Overview

This problem asks us to find the step in which the block in each cell collapses.
The key insight is that the collapse time can be thought of as the “minimum sum of the durability values of the cells along a path from the outer boundary to that cell.”

Analysis

Let \(T(v)\) be the step at which cell \(v\) collapses.

First, the boundary cells are exposed to the elements from the very beginning.
Therefore, a boundary cell with durability \(C_v\) will decrease by \(1\) in each step starting from step \(1\), and will collapse at exactly step \(C_v\).

That is, for boundary cells:

\[ T(v) = C_v \]

Next, let’s consider the inner cells.

Suppose an adjacent cell \(u\) collapses at step \(T(u)\).
Then, cell \(v\) will be exposed to the elements starting from the next step, \(T(u)+1\).

Since its durability is \(C_v\), it will decrease \(C_v\) times from that point and then collapse, so the collapse step will be:

\[ T(u) + C_v \]

Therefore, cell \(v\) will be eroded by the adjacent cell that collapses the earliest, so we can express it as:

\[ T(v) = C_v + \min_{u \in \text{adjacent cells}} T(u) \]

Looking at this from a different perspective, this transforms the problem into:

• Treat the boundary cells as the starting points.
• The cost to enter a cell is its durability value \(C_{i,j}\).
• Find the shortest distance to each cell.

In other words, the collapse step of cell \(v\) is:

\[ T(v) = \min_{\text{path from boundary to } v} \sum_{\text{cell } x \text{ on the path}} C_x \]

For example, if you reach a target cell from a boundary cell by passing through cells with durabilities \(3, 5, 2\) in order, the target cell will collapse at step:

\[ 3 + 5 + 2 = 10 \]

Naive Simulation is Too Slow

If we simulate the process by checking the cells exposed to the elements and reducing their durability at each step, it will take too much time because the maximum durability can be up to \(10^9\).

Furthermore, since the maximum collapse step is the sum of durabilities along the path, it can be up to around:

\[ 500 \times 500 \times 10^9 \]

A step-by-step simulation will not run in time.

Therefore, we model this as a shortest path problem on a weighted graph and solve it using Dijkstra’s algorithm.

Algorithm

We consider each cell of the grid as a vertex.

Edges are directed between adjacent cells (up, down, left, right). The cost of moving from cell \(v\) to an adjacent cell \(u\) is the durability of the destination cell, \(C_u\).

Since the boundary cells are exposed to the elements from the beginning, their initial distance is set to their own durability values.

The procedure is as follows:

1. Initialize the collapse step dist for each cell to infinity.
2. For each boundary cell, set dist = C and push it into the priority queue.
3. Perform Dijkstra’s algorithm:
   • Pop the cell with the smallest collapse step.
   • For each cell adjacent to it, update its value with:

\[ \text{New Candidate} = \text{Collapse Step of Current Cell} + \text{Durability of Adjacent Cell} \]

1. Output the dist of the cells specified in the queries.

This dist will be the step number at which the cell collapses.

Complexity

Let \(N = H \times W\).

The number of edges in the grid is at most around \(4N\). Since we use Dijkstra’s algorithm:

• Time Complexity: \(O(HW \log(HW) + Q)\)
• Space Complexity: \(O(HW + Q)\)

Key Implementation Points

• The cell \((r, c)\) is flattened to a 1D index using idx = r * W + c.

• The priority queue stores pairs of (collapse step, cell index).

• In Dijkstra’s algorithm, outdated information can remain in the queue. Therefore, if the popped value does not match the current dist, ignore it.

• When updating adjacent cells, add + C[adjacent cell] instead of +1.

  • This is because erosion starts from the step after the adjacent cell collapses, and it takes steps equal to the durability of the current cell to collapse.

• In the code, an optimization is included to terminate Dijkstra’s algorithm early once all inner cells specified in the queries have been determined. The answers for boundary cells are already determined as C from the start.

  Source Code

import sys
from heapq import heappush, heappop, heapify

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    p = 0

    H = data[p]
    W = data[p + 1]
    p += 2

    N = H * W
    C = data[p:p + N]
    p += N

    Q = data[p]
    p += 1

    queries = [0] * Q
    target = bytearray(N)
    remain = 0

    bottom = H - 1
    right = W - 1

    for qi in range(Q):
        r = data[p] - 1
        c = data[p + 1] - 1
        p += 2

        idx = r * W + c
        queries[qi] = idx

        if r != 0 and r != bottom and c != 0 and c != right:
            if target[idx] == 0:
                target[idx] = 1
                remain += 1

    del data

    if remain == 0:
        sys.stdout.write("\n".join([str(C[idx]) for idx in queries]))
        return

    INF = 10 ** 18
    dist = [INF] * N
    heap = []

    # top row
    for j in range(W):
        v = C[j]
        dist[j] = v
        heap.append((v, j))

    # bottom row
    base = N - W
    for j in range(base, N):
        v = C[j]
        dist[j] = v
        heap.append((v, j))

    # left and right columns excluding corners
    last_col = W - 1
    for idx in range(W, base, W):
        v = C[idx]
        dist[idx] = v
        heap.append((v, idx))

        idx2 = idx + last_col
        v = C[idx2]
        dist[idx2] = v
        heap.append((v, idx2))

    heapify(heap)

    pop = heappop
    push = heappush
    c_arr = C
    d_arr = dist
    tgt = target
    width = W
    total = N
    lower_limit = N - W
    rem = remain

    while heap:
        d, v = pop(heap)
        if d != d_arr[v]:
            continue

        if tgt[v]:
            tgt[v] = 0
            rem -= 1
            if rem == 0:
                break

        if v >= width:
            u = v - width
            nd = d + c_arr[u]
            if nd < d_arr[u]:
                d_arr[u] = nd
                push(heap, (nd, u))

        if v < lower_limit:
            u = v + width
            nd = d + c_arr[u]
            if nd < d_arr[u]:
                d_arr[u] = nd
                push(heap, (nd, u))

        col = v % width

        if col:
            u = v - 1
            nd = d + c_arr[u]
            if nd < d_arr[u]:
                d_arr[u] = nd
                push(heap, (nd, u))

        if col != last_col:
            u = v + 1
            nd = d + c_arr[u]
            if nd < d_arr[u]:
                d_arr[u] = nd
                push(heap, (nd, u))

    sys.stdout.write("\n".join([str(dist[idx]) for idx in queries]))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.