問題
W \times H 方格,每个方格上都写有一个数字。左上角的正方形 (1, 1),右下方块 表示为 (W, H) 。 来自
质量 从 S 到 T 的路径是一系列方块,其第一个点和最后一个点是 S 和 按字典顺序比较 T ,并且该列中的任何两个连续单元格都是相邻的。这里,相邻意味着共享边缘。路线的成本是路线中所包含的方块中写入的数字的总和。
写在黑板上的数字和 给定 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) 的路线的最小成本。
制約
- 1 \leq W \leq 10
- 2 \leq H \leq 10^4
- 1 \leq Q \leq 10^5
- 0 \leq A_{x,y} \leq 10^9
- 1 \leq SX_i, TX_i \leq W
- 1 \leq SY_i, TY_i \leq H
- (SX_i, SY_i) \neq (TX_i, TY_i)
部分点
针对该问题的判断设置了一组50分的测试用例。该组中包含的测试用例输入还满足以下条件。
-
W=2W \leq 2
入力例 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