/ 
Time Limit: 5 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
東西南北方向に H\times W 個の区画に区切られた街があり、各区画にはちょうど 1 つのビルが立っています。
具体的には北から i 番目 (1\leq i\leq H) かつ西から j 番目 (1\leq j\leq W) の区画（以下、区画 (i,j) とよぶ）には F_{i,j} 階建てのビルがあります。
高橋君には 2 種類の移動方法があり、区画 (i,j) のビルの X 階 (1\leq X\leq F_{i,j}) にいるとき、そこから次のような移動が可能です。
- 同じビルの中の 1 つ上の階または 1 つ下の階へ 階段 を使って移動する。ただし、1 階から 1 つ下の階への移動および、F_{i,j} 階から 1 つ上の階への移動はできない。
- 東西南北に隣接する区画にあるビルのうち、 X 階建て以上であるものを 1 つを選び、そのビルの X 階へ （上空）通路 を使って移動する。
ただし、区画 (i,j) と区画 (i',j') が東西南北に隣接するとは、\lvert i-i'\rvert+\lvert j-j'\rvert=1 であることをさします。
Q 個の質問が与えられるので、それぞれの質問に答えてください。i 個目 (1\leq i\leq Q) の質問は次のようなものです。
区画 (A_i,B_i) にあるビルの Y_i 階から、区画 (C_i,D_i) にあるビルの Z_i 階へ高橋君が移動する時に、 階段 を使う回数としてあり得る最小の値を求めよ。
ここで、階段を使う回数は 1 つ上の階または 1 つ下の階へ移動するたびにカウントされ、同じビルの中でも重複してカウントされるものとする。 (例えば、あるビルを 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
1 番目の質問について、例えば以下のように移動すると階段を合計で 10 回使用して、 区画 (1,1) のビルの 10 階から区画 (3,1) のビルの 6 階へ移動することができます。
- 通路を使って、区画 (1,1) のビルの 10 階から区画 (1,2) のビルの 10 階へ移動する。
- 階段を 4 回使って、区画 (1,2) のビルの 10 階から 6 階へ移動する。
- 通路を使って、区画 (1,2) のビルの 6 階から区画 (1,3) のビルの 6 階へ移動する。
- 階段を 3 回使って、区画 (1,3) のビルの 6 階から 3 階へ移動する。
- 通路を使って、区画 (1,3) のビルの 3 階から区画 (2,3) のビルの 3 階へ移動する。
- 通路を使って、区画 (2,3) のビルの 3 階から区画 (3,3) のビルの 3 階へ移動する。
- 階段を 3 回使って、区画 (3,3) のビルの 3 階から 6 階へ移動する。
- 通路を使って、区画 (3,3) のビルの 6 階から区画 (3,2) のビルの 6 階へ移動する。
- 通路を使って、区画 (3,2) のビルの 6 階から区画 (3,1) のビルの 6 階へ移動する。
階段の使用回数が 9 回以下となるように、区画 (1,1) のビルの 10 階から区画 (3,1) のビルの 6 階へ移動することはできないため、10 を出力します。
2 番目の質問については、区画 (1,2) のビルへ通路を用いて移動した後に、階段を 2 回用いて 6 階から 4 階へ下りると、階段を 2 回使用することで、区画 (1,1) のビルの 6 階から区画 (1,2) のビルの 4 階へ移動することができます。
Score : 600 points
Problem Statement
There is a city divided into H \times W blocks in the north-south-east-west directions, and there is exactly one building in each block.
Specifically, in the block at the i-th row from the north (1\leq i\leq H) and the j-th column from the west (1\leq j\leq W) (hereafter referred to as block (i,j)), there is a building of F_{i,j} floors.
Takahashi has two ways of moving. If he is on the X-th floor (1\leq X\leq F_{i,j}) of the building in block (i,j), he can:
- Move up or down one floor within the same building using stairs. If X=1, he cannot move down; if X=F_{i,j}, he cannot move up.
- Choose a building with at least X floors in a cardinally adjacent block, and move to the X-th floor of that building using a (sky) walkway.
Here, two blocks (i,j) and (i',j') are cardinally adjacent if and only if \lvert i - i'\rvert + \lvert j - j'\rvert = 1.
You are given Q queries to be answered. The i-th query (1\leq i\leq Q) is the following.
Find the minimum possible number of times that Takahashi uses stairs to move from the Y_i-th floor of the building in block (A_i,B_i) to the Z_i-th floor of the building in block (C_i,D_i).
The count of times using stairs is incremented each time he moves up or down one floor, possibly multiple times within the same building. (For example, moving from the 1st floor to the 6th floor of a building counts as 5 uses of stairs.)
Note that he does not have to minimize the number of times he uses walkways.
Constraints
- 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)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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
Output
Print Q lines. The i-th line should contain the answer to the i-th query as an integer.
Sample Input 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
Sample Output 1
10 2
For the first query, for example, it is possible to move from the 10th floor of the building in block (1,1) to the 6th floor of the building in block (3,1) by using stairs a total of 10 times, in the following manner:
- Move from the 10th floor of the building in block (1,1) to the 10th floor of the building in block (1,2) via a walkway.
- Use stairs 4 times to go from the 10th floor down to the 6th floor of the building in block (1,2).
- Move from the 6th floor of the building in block (1,2) to the 6th floor of the building in block (1,3) via a walkway.
- Use stairs 3 times to go from the 6th floor down to the 3rd floor of the building in block (1,3).
- Move from the 3rd floor of the building in block (1,3) to the 3rd floor of the building in block (2,3) via a walkway.
- Move from the 3rd floor of the building in block (2,3) to the 3rd floor of the building in block (3,3) via a walkway.
- Use stairs 3 times to go from the 3rd floor up to the 6th floor of the building in block (3,3).
- Move from the 6th floor of the building in block (3,3) to the 6th floor of the building in block (3,2) via a walkway.
- Move from the 6th floor of the building in block (3,2) to the 6th floor of the building in block (3,1) via a walkway.
It is impossible to make this journey using at most 9 uses of stairs, so we output 10.
For the second query, if you first use a walkway to go to the building in block (1,2), and then use the stairs twice to go from the 6th floor down to the 4th floor, it is possible to move from the 6th floor of the building in block (1,1) to the 4th floor of the building in block (1,2) by using the stairs twice.