← 返回题目列表

AtCoder · tenka1_2013_final_c

C. Tenkaichi 拼图琐事

中文机器翻译题面 查看原题

問題文

拼图艺术家 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 如下表所示。
    NMQ
    1571000
    2751000
    3851000
    4581000
    5661000
    6661000
    756500
    865500
    955500
    1046500
    1164500
    1245200
    1354200
    1444100
    154480
    164470
    174350
    183440
    193425
    203325
    213315
    222310
    23237
    24225
    25223

入出力例 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