AT_tenka1_2013_final_c 天下一ジグソーパズルみたび

受高桥君恶作剧的启发，拼图作家秀平君设计了一款拼图，将「天下一程序员大赛」的海报分割成 $N \times M$ 块。 每块拼图相邻边的形状设计为一个凸出一个凹进，而外边缘则是平的。秀平君想编写一个程序，通过尝试连接两块拼图的边来找到原始海报的正确拼法。 程序的输入格式如下： > $ N $ $ M $ $ Q $ $ P_{1, 1} $ $ P_{1, 2} $ $ P_{1, 3} $ $ P_{1, 4} $ $ P_{2, 1} $ $ P_{2, 2} $ $ P_{2, 3} $ $ P_{2, 4} $ ... $ P_{N \times M, 4} $ - $N$ 和 $M$ 分别表示拼图的行数和列数（$2 \leq N, M \leq 8$），$Q$ 是询问的最大次数（$3 \leq Q \leq 10000$）。 - 随后的 $N \times M$ 行数据中，每行包含描述第 $i$ 块拼图四边形状的信息，$P_{i, 1}$、$P_{i, 2}$、$P_{i, 3}$、$P_{i, 4}$分别表示上边、右边、下边和左边的形状，其中 $0$ 表示直线，$1$ 表示凸边，$2$ 表示凹边。 程序可以按照以下查询格式，通过标准输出检查两块拼图的边是否能连接： > ? $ a $ $ d_a $ $ b $ $ d_b $ - 询问第 $a$ 块拼图的 $d_a$ 方向边与第 $b$ 块拼图的 $d_b$ 方向边是否能够正确连接。 - 其中，$1 \leq a, b \leq N \times M$。 - $d_a$ 和 $d_b$ 指定边的方向，取值：上边为 $1$、右边为 $2$、下边为 $3$、左边为 $4$。 - 如果两边能正确连接，应答程序会输出 `yes`，否则输出 `no`。 拼图的最终排列结果需要输出为： > ! $ p_{1, 1} $ $ d_{1, 1} $ $ p_{1, 2} $ $ d_{1, 2} $ ... $ p_{1, M} $ $ d_{1, M} $ ... $ p_{N, M} $ $ d_{N, M} $ - $i$ 行 $j$ 列的拼图块编号为 $p_{i, j}$，并且其上边朝向 $d_{i, j}$ 。 - $d_{i, j}$ 的方向同样为：上 $1$、右 $2$、下 $3$、左 $4$。 - 整个拼图的方向不要求绝对一致，旋转 180 度是允许的。如果 $N = M$，则 90 度或 270 度的旋转也可以接受。 题目提供了一些特殊规则下的部分分数机制。例如，若确保 $Q = 10000$ 的输入答案正确，即可获得 50 分，以下其他条件以此类推： | $N$ | $M$ | $Q$ | |---|---|---| | 1 | 5 | 71000 | | 2 | 7 | 51000 | | 3 | 8 | 51000 | | 4 | 5 | 81000 | | 5 | 6 | 61000 | | 6 | 6 | 61000 | | 7 | 5 | 6500 | | 8 | 6 | 500 | | 9 | 5 | 500 | | 10 | 4 | 6500 | | 11 | 6 | 4500 | | 12 | 4 | 5200 | | 13 | 5 | 4200 | | 14 | 4 | 4100 | | 15 | 4 | 480 | | 16 | 4 | 470 | | 17 | 4 | 350 | | 18 | 3 | 440 | | 19 | 3 | 425 | | 20 | 3 | 325 | | 21 | 3 | 315 | | 22 | 2 | 310 | | 23 | 2 | 37 | | 24 | 2 | 25 | | 25 | 2 | 23 | 示例输入输出： ``` 输入: 2 2 100 0 0 1 2 0 1 2 0 输出: ? 1 4 2 2 no ? 1 3 2 3 yes ! 1 4 2 2 4 1 3 2 ```

无

无

- $2 \leq N, M \leq 8$ - $3 \leq Q \leq 10000$ **本翻译由 AI 自动生成**