東京大学プログラミングコンテスト2012

I - 最短路クエリ


Time limit時間制限 : 6sec / Memory limitメモリ制限 : 512MB

問題

W \times H のグリッド状に区切られた盤面があり,各マスには数字が書かれている.左上のマスを (1, 1),右下のマスを (W, H) と表す.

マス S からマス T への経路とは,マスの列であって,最初と最後が ST であり,かつ列において連続する任意の 2 つのマスは隣接しているようなものである.ここで,隣接するとは,辺を共有することを指す.経路のコストとは,経路に含まれるマスに書かれている数字の合計である.

盤面に書かれた数字と Q 個のマスの対が与えられたとき,各マスの対 (SX_i, SY_i), (TX_i, TY_i) に対し,マス (SX_i, SY_i) からマス (TX_i, TY_i) への経路のコストの最小値を答えるプログラムを出力せよ.


入力

W H Q
A_{1,1} A_{2,1} ... A_{W,1}
...
A_{1,H} A_{2,H} ... A_{W,H}
SX_1 SY_1 TX_1 TY_1
...
SX_Q SY_Q TX_Q TY_Q

入力の最初の行には,縦幅 H と横幅 W とクエリの個数 Q が与えられる.

続く H 行には,盤面に書かれている数字が与えられる. y 行目の x 個目の数字 A_{x,y} はマス (x, y) に書かれた数字である.

さらに続く Q 行に,マスの対 (SX_i, SY_i), (TX_i, TY_i) が書かれている.

出力

各行に,各マスの対に対する経路のコストの最小値を出力せよ. 即ち,i 行目に,マス (SX_i, SY_i) からマス (TX_i, TY_i) への経路のコストの最小値を出力せよ.

制約

部分点

この問題の判定には,50 点分のテストケースのグループが設定されている. このグループに含まれるテストケースの入力は追加で以下の条件を満たす.


入力例 1

2 5 4
0 1
0 1
0 0
1 0
1 0
1 1 2 5
2 1 1 5
1 3 2 3
1 5 1 1

入力例 1 に対する出力例

0
2
0
1

入力例 2

3 6 5
1 9 2
3 4 1
2 5 3
4 2 2
3 1 5
2 6 3
1 1 3 1
1 1 3 6
1 6 3 6
1 3 3 4
2 6 3 2

入力例 2 に対する出力例

11
21
11
10
15

Submit提出する