D - 最短絡問題 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

H 行 W 列のマス目に区切られた部屋がある。i (1 ≦ i ≦ H) 行目 j (1 ≦ j ≦ W) 列目のマスをマス (i,j) と呼ぶことにする。マス目とマス目の間には扉があり、扉を開閉するときのコストが定まっている。扉を開閉するときのコストは全て 1 以上の整数である。全ての i (2 ≦ i ≦ H), j (2 ≦ j ≦ W) について、以下のことが成り立っている。

  • マス (i-1,j-1) とマス (i-1,j) の間の扉の開閉コストを A とする。
  • マス (i,j-1) とマス (i,j) の間の扉の開閉コストを B とする。
  • マス (i-1,j-1) とマス (i,j-1) の間の扉の開閉コストを C とする。
  • マス (i-1,j) とマス (i,j) の間の扉の開閉コストを D とする。
  • このとき、A+D = B+C かつ A+C ≦ B+D が成り立つ。

マス (si,sj) からマス (ti,tj) まで、上下左右に隣り合うマスに移動することを繰り返して行くときにかかる扉の開閉コストの和の最小値を dist(si,sj,ti,tj) と呼ぶことにする。ただし、隣り合うマスに移動するときにはそれらのマスの間にある扉の開閉コストがかかるものとする。また、任意の i,j に対して、dist(i,j,i,j) = 0 であるとして良い。

あなたは、H と W の値は知っているが、扉の開閉コストの情報は何も知らない。あなたは最初に、

  • dist(si,sj,ti,tj) の値はいくつですか？

という形式の質問をちょうど H \times W 回行う。そしてその後、同様の形式の Q 個の質問に答えなければならない。

入出力

まず、マス目の行数・列数と質問の個数を表す 3 つの整数 H (1 ≦ H ≦ 20), W (1 ≦ W ≦ 20), Q (1 ≦ Q ≦ 100) が空白区切りで標準入力に与えられる。

H W Q

続いて、あなたのプログラムはちょうど H \times W 回の質問を行わなければならない。

各質問ではまず、4 つの整数 si (1 ≦ si ≦ H), sj (1 ≦ sj ≦ W), ti (1 ≦ ti ≦ H), tj (1 ≦ tj ≦ W) を空白区切りで出力する。これは、「dist(si,sj,ti,tj) の値はいくつですか？」という質問を表す。

si sj ti tj

すると、あなたのプログラムには dist(si,sj,ti,tj) の値が与えられる。 いかなる場合も dist(si,sj,ti,tj) が 10^9 を超えることはないことが保証される。

H \times W 回の質問が終わると、あなたのプログラムは Q 個の質問に答えなければならない。

各質問ではまず、4 つの整数 Si (1 ≦ Si ≦ H), Sj (1 ≦ Sj ≦ W), Ti (1 ≦ Ti ≦ H), Tj (1 ≦ Tj ≦ W) が空白区切りで与えられる。これは、「dist(Si,Sj,Ti,Tj) の値はいくつですか？」という質問を表す。

Si Sj Ti Tj

続いて、あなたのプログラムは dist(Si,Sj,Ti,Tj) の値を出力しなければならない。

Q 個の質問に答え終われば、 あなたのプログラムは直ちに終了しなければならない。 終了しなかった場合のジャッジ結果は不定である。

また、正しくない出力をした場合の結果も不定である（必ずしも WA になるとは限らない）。

あなたのプログラムが Q 個の質問全てに正しく答えて終了した場合、正答とみなされる。

出力した後に、出力をflushしなければならないことに注意せよ。flushしなかった場合、TLEとなることがある。

各言語での入出力の方法は過去の AtCoder で出題されている問題 (リンク: ABC 019 D: 高橋くんと木の直径) を参考にしてもよい。

入出力例

説明 プログラムの出力 プログラムへの入力
マス目の行数・列数と質問の個数が与えられている。 2 2 2
dist(1,1,2,2) の値を質問している。 1 1 2 2
質問の答えが与えられている。 6
dist(1,1,2,2) の値を再び質問している。 1 1 2 2
質問の答えが与えられている。 6
dist(2,1,2,1) の値を質問している。 2 1 2 1
質問の答えが与えられている。 0
dist(2,2,1,1) の値を質問している。 2 2 1 1
質問の答えが与えられている。 6
dist(1,1,2,2) の値を質問されている。 1 1 2 2
質問の答えを出力している。 6
dist(1,2,1,2) の値を質問されている。 1 2 1 2
質問の答えを出力している。 0