問題文
拼图艺术家 Shohei 在看到被高桥恶作剧撕碎的天下程序员大赛海报后受到启发。 我制作了一个拼图游戏,分为N \times M 块。
纵向和横向相邻的片材的一侧为凸形,另一侧为凹形,且外边缘是平直的。
Shohei 决定创建一个程序来恢复原始海报,方法是尝试查看海报的两侧是否可以粘在一起,找到最初附着的一侧。
入出力
首先,按照以下格式从标准输入给出输入。
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, 1} P_{N \times M, 2} P_{N \times M, 3} 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}。然而,P_{i, j} = 0是一条直线,P_{i, j} = 1是凸的,P_{i, j} = 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_{2, 1} d_{2, 1} p_{2, 2} d_{2, 2} ... p_{2, M} d_{2, M}
...
p_{N, 1} d_{N, 1} p_{N, 2} d_{N, 2} ... 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 ,您将在总分 160 分中获得 50 分作为部分分。 如果您正确回答
- Q = 3000 ,您将获得额外的60分,作为160分中的部分分。
- 剩余 50 分有 25 个输入,每个正确输入给出 2 分作为部分分。每个输入的 N, M, Q 如下表所示。
N M Q 1 5 7 1000 2 7 5 1000 3 8 5 1000 4 5 8 1000 5 6 6 1000 6 6 6 1000 7 5 6 500 8 6 5 500 9 5 5 500 10 4 6 500 11 6 4 500 12 4 5 200 13 5 4 200 14 4 4 100 15 4 4 80 16 4 4 70 17 4 3 50 18 3 4 40 19 3 4 25 20 3 3 25 21 3 3 15 22 2 3 10 23 2 3 7 24 2 2 5 25 2 2 3
入出力例 1
| プログラムの出力 | プログラムへの入力 |
|---|---|
| 2 2 100 0 0 1 2 0 1 2 0 0 0 2 2 1 1 0 0 | |
| ? 1 4 2 2 | |
| no | |
| ? 1 3 2 3 | |
| yes | |
| ! 1 4 2 2 4 1 3 2 |