分数: 600 点
问题陈述
有一个城市分为 H \times W 南北向的街区,每个街区内只有一栋建筑物。
具体来说,在 i从北数第 3 行 (1\leq i\leq H) 和 j从西数第 3 列 (1\leq j\leq W) (以下简称块 (i,j)),有一座建筑物 F_{i,j} 楼层。
高桥有两种移动方式。如果他在 X-楼 街区内建筑物的 (1\leq X\leq F_{i,j}) 街区内建筑物的 (i,j),他可以:
- 使用以下命令在同一建筑物内向上或向下移动一层 楼梯。如果 X=1,他无法向下移动;如果 X=F_{i,j},他无法向上移动。
- 选择一栋至少具有 X 基本相邻街区中的楼层,然后移动到 X该建筑物的第 3 层使用 (天空)走道.
这里,两个街区 (i,j) 和 (i',j') 基本相邻当且仅当 \lvert i - i'\rvert + \lvert j - j'\rvert = 1.
你被给予 Q 疑问有待解答。的 i第一个查询 (1\leq i\leq Q) 如下。
求高桥使用的最少可能次数 楼梯 从 Y_i街区大楼的第 3 层 (A_i,B_i) 到 Z_i街区大楼的第 3 层 (C_i,D_i).
每次他上下一层楼时,使用楼梯的次数都会增加,甚至可能在同一建筑物内多次。 (例如,从建筑物的 1 楼移动到 6 楼算作 5 楼梯的用途。)
请注意,他不必尽量减少使用走道的次数。
约束
- 1\leq H \leq 500
- 1\leq W \leq 500
- 1\leq F_{i,j} \leq 10^6
- 1\leq Q\leq 2\times 10^5
- 1\leq A_i,C_i\leq H
- 1\leq B_i,D_i\leq W
- 1\leq Y_i\leq F_{A_i,B_i}
- 1\leq Z_i\leq F_{C_i,D_i}
- (A_i,B_i,Y_i)\neq (C_i,D_i,Z_i)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
H W
F_{1,1} F_{1,2} \ldots F_{1,W}
F_{2,1} F_{2,2} \ldots F_{2,W}
\vdots
F_{H,1} F_{H,2} \ldots F_{H,W}
Q
A_1 B_1 Y_1 C_1 D_1 Z_1
A_2 B_2 Y_2 C_2 D_2 Z_2
\vdots
A_Q B_Q Y_Q C_Q D_Q Z_Q
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i-第一个查询作为整数。
示例输入 1
3 3 12 10 6 1 1 3 8 6 7 2 1 1 10 3 1 6 1 1 6 1 2 4
示例输出 1
10 2
对于第一个查询,例如可以从街区内建筑物的 10 层移动 (1,1) 至该街区大楼6楼 (3,1) 通过使用楼梯总共 10 次,按以下方式进行:
- 从该街区大楼10楼搬迁 (1,1) 至该街区大楼10楼 (1,2) 通过走道。
- 使用楼梯 4 该街区从10楼到6楼的次数 (1,2).
- 从该街区大楼6楼搬迁 (1,2) 至该街区大楼6楼 (1,3) 通过走道。
- 使用楼梯 3 该街区大楼从六楼到三楼的次数 (1,3).
- 从该街区大楼3楼搬迁 (1,3) 至该街区大楼3楼 (2,3) 通过走道。
- 从该街区大楼3楼搬迁 (2,3) 至该街区大楼3楼 (3,3) 通过走道。
- 使用楼梯 3 该街区大楼从3楼到6楼的次数 (3,3).
- 从该街区大楼6楼搬迁 (3,3) 至该街区大楼6楼 (3,2) 通过走道。
- 从该街区大楼6楼搬迁 (3,2) 至该街区大楼6楼 (3,1) 通过走道。
最多使用此行程是不可能的 9 使用楼梯,所以我们输出 10.
对于第二个查询,如果您首先使用走道前往街区中的建筑物 (1,2),然后使用两次楼梯从六楼下到四楼,可以从大楼的六楼移动到街区 (1,1) 至该街区大楼4楼 (1,2) 两次使用楼梯。