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

Time Limit: 2 sec / Memory Limit: 64 MB


問題文

高橋君のいたずらによりバラバラにされた天下一プログラマーコンテストのポスターを見て触発されたパズル作家のショウヘイ君は、天下一プログラマーコンテストのポスターを下図のようにN \times M のピースに分割したジグソーパズルを作った。

上下左右に隣り合うピースの一辺は一方が凸に他方が凹になっており、外周の辺は直線になっている。

ショウヘイ君は一度バラバラにしたポスターを、2つの辺がくっつくかどうかを試していき元々くっついていた辺を探すことで、元のポスターを復元するプログラムを制作することにした。


入出力

まず、入力が以下の形式で標準入力から与えられる。

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は凹を意味する。

あなたのプログラムは、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 の入力に正解すると、160 点満点に対して部分点として、上記とは別に 60 点が与えられる。
  • 残り 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