D - 侵食される遺跡 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は、H 行 W 列のグリッド状に石のブロックが並んだ古代遺跡の調査を行っています。各マスには石のブロックが置かれており、上から i 行目、左から j 列目のブロックの 耐久値 は C_{i,j} です。

グリッドの外側の領域には常に風雨が吹き荒れています。ここで「グリッドの外側」とは、1 行目〜H 行目かつ 1 列目〜W 列目の範囲の外にある領域を指します。長い年月が経ち、石のブロックは風雨に触れている面から徐々に侵食されていきます。

石ブロックが「風雨にさらされている」とは、そのブロックの上下左右 4 方向の隣接マスのうち少なくとも 1 つが、グリッドの外側であるか、または空きマス（石ブロックが崩壊して何もなくなったマス）であることを意味します。初期状態では空きマスは存在しません。特に、グリッドの端（1 行目、H 行目、1 列目、W 列目）にあるブロックは、グリッドの外側に隣接しているため、初期状態から風雨にさらされています。

侵食は ステップ を単位として進行します。ステップには 1 から順に番号が付けられています。各ステップでは、以下の処理 1, 処理 2 がこの順に 1 回ずつ 行われます。

  1. 耐久値の減少： そのステップの開始時点で風雨にさらされているすべての石ブロックの耐久値が、同時に 1 だけ減少する。風雨にさらされていない石ブロックの耐久値は変化しない。
  2. 崩壊判定： 処理 1 の結果、耐久値が 0 になった石ブロックはすべて 同時に 崩壊し、そのマスは空きマスとなる。

同一ステップ内で連鎖的な崩壊は起こりません。すなわち、処理 2 で崩壊が起きた結果、新たに風雨にさらされるようになったブロックがあっても、そのブロックの耐久値がこのステップ中にさらに減少することはありません。新たに風雨にさらされるようになったブロックは、次のステップの処理 1 から耐久値の減少が始まります。

グリッドは有限であり、外周のブロックから順に侵食が内側へ進行するため、すべてのブロックは有限ステップで必ず崩壊します。したがって、どのマスについても崩壊するステップ番号は有限の正整数として定まります。

高橋君は、調査対象として指定された Q 個のマスについて、それぞれのマスにある石ブロックが崩壊するステップ番号を調べることにしました。

k 番目の調査対象は、上から R_k 行目、左から K_k 列目のマスです。Q 個の調査対象それぞれについて、そのマスの石ブロックが崩壊するステップ番号を求めてください。

制約

  • 1 \leq H \leq 500
  • 1 \leq W \leq 500
  • 1 \leq C_{i,j} \leq 10^9
  • 1 \leq Q \leq 10^5
  • 1 \leq R_k \leq H
  • 1 \leq K_k \leq W
  • クエリで指定されるマスは重複することがある。
  • 入力はすべて整数である。

入力

H W
C_{1,1} C_{1,2} \cdots C_{1,W}
C_{2,1} C_{2,2} \cdots C_{2,W}
\vdots
C_{H,1} C_{H,2} \cdots C_{H,W}
Q
R_1 K_1
R_2 K_2
\vdots
R_Q K_Q
  • 1 行目には、遺跡の行数 H と列数 W がスペース区切りで与えられる。
  • 続く H 行では、遺跡の各マスの石ブロックの耐久値が与えられる。このうち i 行目（1 \leq i \leq H）には、グリッドの i 行目の耐久値 C_{i,1}, C_{i,2}, \ldots, C_{i,W} がスペース区切りで与えられる。
  • その次の行には、クエリの個数 Q が与えられる。
  • 続く Q 行にわたり、各クエリが与えられる。k 番目のクエリ（1 \leq k \leq Q）では、問い合わせ対象の行番号 R_k と列番号 K_k がスペース区切りで与えられ、上から R_k 行目、左から K_k 列目のマスの石ブロックについて問う。

出力

Q 行出力せよ。k 行目（1 \leq k \leq Q）には、上から R_k 行目、左から K_k 列目の石ブロックが崩壊するステップの番号を整数で出力せよ。

入力例 1

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

出力例 1

1
6
4
3
1

入力例 2

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

出力例 2

4
1
3
2
5
3

入力例 3

6 7
3 8 2 6 4 7 1
5 12 9 10 3 11 4
6 14 20 18 13 9 2
4 15 22 17 16 8 5
7 10 6 12 9 14 3
2 5 8 4 6 1 9
12
1 1
1 7
2 3
3 4
4 3
4 5
5 2
6 6
3 1
6 7
2 6
5 5

出力例 3

3
1
11
34
36
29
15
1
6
9
15
15

入力例 4

12 12
5 18 7 21 9 30 12 25 6 17 11 4
14 40 33 28 19 45 37 31 22 26 35 8
10 29 55 48 42 60 51 46 39 44 20 13
16 34 58 70 65 72 69 63 57 50 27 15
23 41 62 80 95 90 88 76 61 53 32 18
9 36 59 84 100 120 110 92 74 56 38 24
20 43 67 89 115 130 125 101 83 64 47 28
12 31 54 78 96 112 105 87 71 49 30 19
8 27 45 66 79 91 86 73 58 42 25 14
6 22 39 52 68 77 70 55 43 33 16 10
11 24 30 37 46 59 48 40 29 21 13 7
3 15 9 26 12 34 18 23 5 20 8 2
20
1 1
1 12
12 1
12 12
6 6
7 7
5 8
8 5
3 4
10 10
2 2
11 11
4 9
9 4
6 1
1 6
12 9
7 12
5 5
5 5

出力例 4

5
4
3
2
408
448
240
271
97
59
54
20
124
146
9
30
5
28
230
230

入力例 5

1 1
1000000000
5
1 1
1 1
1 1
1 1
1 1

出力例 5

1000000000
1000000000
1000000000
1000000000
1000000000

Score : 400 pts

Problem Statement

Takahashi is investigating ancient ruins where stone blocks are arranged in a grid with H rows and W columns. Each cell contains a stone block, and the block at the i-th row from the top and j-th column from the left has a durability of C_{i,j}.

Wind and rain are constantly raging in the area outside the grid. Here, "outside the grid" refers to the region outside the range of rows 1 through H and columns 1 through W. Over many years, the stone blocks gradually erode starting from the surfaces that come into contact with the wind and rain.

A stone block is said to be "exposed to the wind and rain" if at least one of its four orthogonally adjacent cells (up, down, left, right) is outside the grid or is an empty cell (a cell where a stone block has collapsed and disappeared). Initially, there are no empty cells. In particular, the blocks on the boundary of the grid (1-st row, H-th row, 1-st column, and W-th column) are adjacent to the outside of the grid, so they are exposed to the wind and rain from the initial state.

Erosion progresses in units of steps, numbered starting from 1. In each step, the following Process 1 and Process 2 are performed once each in this order:

  1. Durability Reduction: The durability of every stone block that is exposed to the wind and rain at the start of this step decreases by 1 simultaneously. The durability of stone blocks not exposed to the wind and rain does not change.
  2. Collapse Check: All stone blocks whose durability becomes 0 as a result of Process 1 collapse simultaneously, and their cells become empty cells.

Cascading collapses do not occur within the same step. That is, even if some blocks become newly exposed to the wind and rain as a result of collapses in Process 2, the durability of those blocks will not decrease further during this step. Newly exposed blocks will begin to have their durability decreased starting from Process 1 of the next step.

Since the grid is finite and erosion progresses inward starting from the outer perimeter, all blocks will inevitably collapse within a finite number of steps. Therefore, the step number at which each cell's block collapses is uniquely determined as a finite positive integer.

Takahashi has decided to investigate the step number at which the stone block collapses for each of Q designated target cells.

The k-th target is the cell at the R_k-th row from the top and K_k-th column from the left. For each of the Q targets, find the step number at which the stone block at that cell collapses.

Constraints

  • 1 \leq H \leq 500
  • 1 \leq W \leq 500
  • 1 \leq C_{i,j} \leq 10^9
  • 1 \leq Q \leq 10^5
  • 1 \leq R_k \leq H
  • 1 \leq K_k \leq W
  • The cells specified by the queries may contain duplicates.
  • All input values are integers.

Input

H W
C_{1,1} C_{1,2} \cdots C_{1,W}
C_{2,1} C_{2,2} \cdots C_{2,W}
\vdots
C_{H,1} C_{H,2} \cdots C_{H,W}
Q
R_1 K_1
R_2 K_2
\vdots
R_Q K_Q
  • The first line contains the number of rows H and the number of columns W of the ruins, separated by a space.
  • The following H lines give the durabilities of the stone blocks at each cell of the ruins. The i-th line (1 \leq i \leq H) contains the durabilities C_{i,1}, C_{i,2}, \ldots, C_{i,W} of the i-th row of the grid, separated by spaces.
  • The next line contains the number of queries, Q.
  • The following Q lines describe the queries. The k-th query (1 \leq k \leq Q) contains the target row number R_k and column number K_k separated by a space, asking about the stone block at the R_k-th row from the top and K_k-th column from the left.

Output

Print Q lines. The k-th line (1 \leq k \leq Q) should contain an integer representing the step number at which the stone block at the R_k-th row from the top and K_k-th column from the left collapses.

Sample Input 1

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

Sample Output 1

1
6
4
3
1

Sample Input 2

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

Sample Output 2

4
1
3
2
5
3

Sample Input 3

6 7
3 8 2 6 4 7 1
5 12 9 10 3 11 4
6 14 20 18 13 9 2
4 15 22 17 16 8 5
7 10 6 12 9 14 3
2 5 8 4 6 1 9
12
1 1
1 7
2 3
3 4
4 3
4 5
5 2
6 6
3 1
6 7
2 6
5 5

Sample Output 3

3
1
11
34
36
29
15
1
6
9
15
15

Sample Input 4

12 12
5 18 7 21 9 30 12 25 6 17 11 4
14 40 33 28 19 45 37 31 22 26 35 8
10 29 55 48 42 60 51 46 39 44 20 13
16 34 58 70 65 72 69 63 57 50 27 15
23 41 62 80 95 90 88 76 61 53 32 18
9 36 59 84 100 120 110 92 74 56 38 24
20 43 67 89 115 130 125 101 83 64 47 28
12 31 54 78 96 112 105 87 71 49 30 19
8 27 45 66 79 91 86 73 58 42 25 14
6 22 39 52 68 77 70 55 43 33 16 10
11 24 30 37 46 59 48 40 29 21 13 7
3 15 9 26 12 34 18 23 5 20 8 2
20
1 1
1 12
12 1
12 12
6 6
7 7
5 8
8 5
3 4
10 10
2 2
11 11
4 9
9 4
6 1
1 6
12 9
7 12
5 5
5 5

Sample Output 4

5
4
3
2
408
448
240
271
97
59
54
20
124
146
9
30
5
28
230
230

Sample Input 5

1 1
1000000000
5
1 1
1 1
1 1
1 1
1 1

Sample Output 5

1000000000
1000000000
1000000000
1000000000
1000000000