AT_future_fif_digital_days_a Polyomino Connection A

在一个 $N \times N$ 的棋盘上，有 $B$ 种多米诺骨牌。棋盘的左上角坐标为 $(0, 0)$，从该位置向下 $i$ 格、向右 $j$ 格的格子坐标为 $(i, j)$。初始情况下，所有的格子都是不可通行的。放置多米诺骨牌后，其上的格子可变为通行状态。棋盘上有 $K$ 个格子有标记，目标是在这些标记处放置多米诺骨牌，使得所有标记的格子连成一片。 例如，在上面的图例中，左上和右上的标记已经连通，但与下方的标记仍未连通。 你可以任意次数地放置同一种多米诺骨牌，但不能旋转骨牌或使其超出棋盘的边界。同一位置不能重叠放置多个多米诺骨牌。每种多米诺骨牌 $b$ 都有一个放置成本 $C_b$，若放置 $m_b$ 个 $b$ 型骨牌，总成本为 $\sum_{b=1}^B C_b m_b$。请在保证标记格子全连通的情况下，使得总成本最小化。

输入包括： - 第一行：三个整数 $N$、$K$ 和 $B$，分别表示棋盘边长、标记的格子数和多米诺骨牌种类数。所有测试用例中，$N$ 均为 50。 - 接下来 $K$ 行，每行两个整数，表示第 $p$ 个标记格子的坐标 $(i_p, j_p)$，满足 $0 \leq i_p < N, 0 \leq j_p < N$。标记格子的坐标都是不同的。 - 随后是 $B$ 种多米诺骨牌的信息，每种骨牌的信息包括： - $n_b$ 和 $m_b$：表示第 $b$ 种多米诺骨牌最小边界框的高度和宽度，保证 $n_1 = m_1 = 1$。 - $C_b$：放置一个第 $b$ 种多米诺骨牌的成本，是一个正整数。 - $s^b_{i,j}$：第 $b$ 种多米诺骨牌的边界框中，第 $i$ 行、第 $j$ 列的格子信息，`#` 表示该位置属于骨牌，`.` 则不属于。每种多米诺骨牌都是连通的。

输出格式为： - 第一行输出使用的多米诺骨牌总数 $m$。 - 接下来 $m$ 行，每行包含使用的多米诺骨牌种类编号 $b_i$（$1 \leq b_i \leq B$）和其边界框的左上角坐标 $(x_i, y_i)$，满足 $0 \leq x_i \leq N-n_{b_i}, 0 \leq y_i \leq N-m_{b_i}$。

### 得分计算 总成本为 $S$ 时，得分计算公式为 $\mathrm{round}(10^8 / S)$。输出不合法的情况（如标记格子未连通、多米诺骨牌超出棋盘、重叠）会被判定为错误（WA）。如果任何一个测试用例不通过，则提交得分记为 0 分。比赛以取得的最高分进行排名，赛后不再进行系统测试。同分情况下，以提交时间较早者为优。 ### 测试用例数 只有 1 个 ### 输入生成说明 问题的测试用例为 1 个，等同于题目的第一个样例输入。你可以计算出结果并直接提交。 ### 辅助工具 - [在线可视化工具与输入生成器](https://img.atcoder.jp/future-fif-digital-days/visYp.html?q=a) - [本地运行版可视化工具与输入生成器](https://img.atcoder.jp/future-fif-digital-days/dd7a70773bb74f0570cdde81b1bf6ee3.zip)：需要 Rust 编译环境以运行。 **本翻译由 AI 自动生成**