← 返回题目列表

AtCoder · abc394_g

G. 密集的建筑物

中文机器翻译题面 查看原题

分数: 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) 两次使用楼梯。