Overview

This problem asks us to find the number of steps it takes for each stone block in a grid to collapse due to weathering/erosion starting from the outside of the grid. By treating the grid as a graph, this problem can be reduced to the “shortest path problem with weights” from the outer boundary to each cell, which can be solved efficiently using Dijkstra’s algorithm.

Analysis

Understanding the Rules

• At each step, the durability of cells exposed to wind and rain decreases by \(1\).
• When the durability becomes \(0\), the cell collapses and becomes an empty cell.
• Cells adjacent to an empty cell will be exposed to wind and rain from the next step (their durability starts to decrease).

Observing Specific Behavior

As an example, let’s consider the relationship between cell \(A\) (durability \(C_A\)) on the outer boundary and its adjacent inner cell \(B\) (durability \(C_B\)).

1. Cell \(A\) is exposed to wind and rain from the beginning. Thus, its durability starts decreasing from step \(1\) and collapses at the end of step \(C_A\).
2. Cell \(B\) starts being exposed to wind and rain from the step after cell \(A\) collapses, which is step \(C_A + 1\).
3. It takes \(C_B\) steps for cell \(B\) to collapse after it starts being exposed. Therefore, cell \(B\) collapses at step \((C_A + 1) + C_B - 1 = C_A + C_B\).

Generalizing this, the step at which a cell \(v\) collapses can be expressed using the collapse step of an adjacent cell \(u\), denoted as \(dist[u]\), as follows: $\(dist[v] = dist[u] + C_v\)$

Since cell \(v\) can be eroded from any of the \(4\) directions (up, down, left, right), the path that reaches it earliest is taken. That is: $\(dist[v] = \min_{u \in \text{adj}(v)} (dist[u]) + C_v\)\( (Note that for cells on the outer boundary, the initial state is \)dist[\text{外周}] = C_{\text{外周}}$).

Limitations of Naive Simulation

If we consider a naive simulation that updates the grid state step by step, the durability \(C_{i,j}\) of each cell can be up to \(10^9\). Thus, the number of steps in the simulation would be huge, and it would not run within the time limit (TLE). Therefore, we need an approach to directly calculate the collapse steps without simulation, focusing on the recurrence relation of the “collapse step” as described above.

Algorithm

This problem can be solved as a shortest path problem on a graph where each cell in the grid is a vertex and adjacent cells are connected by edges.

1. Graph Construction: Let each cell be a vertex \(u\). Add undirected edges between adjacent cells in the \(4\) directions.

2. Applying Dijkstra’s Algorithm:

   • Initialize an array dist that stores the “collapse step count” for each vertex \(u\) with infinity (\(\infty\)).
   • As the initial state, update the dist values of the cells on the outer boundary (\(1\)st row, \(H\)-th row, \(1\)st column, and \(W\)-th column) with their durability \(C_{i,j}\), and add them to a priority queue (heap).
   • Pop the vertex \(u\) with the smallest collapse step count (finalized value \(d = dist[u]\)) from the priority queue.
   • For each vertex \(v\) adjacent to \(u\), if the newly calculated collapse step count \(nd = d + C_v\) is smaller than the current \(dist[v]\), update \(dist[v]\) to \(nd\) and add \((nd, v)\) to the queue.

3. Query Processing: Once the collapse step count dist for all cells is found using Dijkstra’s algorithm, we can answer each query \((R_k, K_k)\) in \(O(1)\) time by outputting the value in dist.

Complexity

• Time Complexity: \(O(HW \log(HW) + Q)\)
  • The number of vertices is \(V = HW\), and the number of edges is \(E \approx 4HW\).
  • Since the complexity of Dijkstra’s algorithm is \(O(E \log V)\), the overall complexity is \(O(HW \log(HW))\).
  • Each of the \(Q\) queries can be answered in \(O(1)\) time, so the total time complexity is \(O(HW \log(HW) + Q)\), which is well within the time limit.
• Space Complexity: \(O(HW)\)
  • We use \(O(HW)\) memory to store the graph’s adjacency list, the dist array, and the priority queue.

Implementation Details

• 1D Array Management: By converting 2D grid coordinates \((r, c)\) into 1D indices using the formula \(r \times W + c\), we simplify the implementation and improve memory efficiency and execution speed.

• Fast I/O: In Python, since the number of inputs and outputs is large (\(Q \le 10^5\)), we can avoid I/O bottlenecks by reading all inputs at once using sys.stdin.read().split() and printing the outputs at once using \n.join().

  Source Code

import heapq
import sys


def main():
    # 入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    H = int(input_data[0])
    W = int(input_data[1])

    # C を1次元配列として取得
    C_flat = [int(x) for x in input_data[2 : 2 + H * W]]

    # 隣接リストの作成
    adj = [[] for _ in range(H * W)]
    for u in range(H * W):
        r = u // W
        c = u % W
        if r > 0:
            adj[u].append(u - W)
        if r < H - 1:
            adj[u].append(u + W)
        if c > 0:
            adj[u].append(u - 1)
        if c < W - 1:
            adj[u].append(u + 1)

    # ダイクストラ法の初期化
    dist = [float("inf")] * (H * W)
    pq = []

    for u in range(H * W):
        r = u // W
        c = u % W
        if r == 0 or r == H - 1 or c == 0 or c == W - 1:
            dist[u] = C_flat[u]
            pq.append((C_flat[u], u))

    heapq.heapify(pq)

    # ダイクストラ法
    while pq:
        d, u = heapq.heappop(pq)

        if d > dist[u]:
            continue

        for v in adj[u]:
            nd = d + C_flat[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))

    # クエリの処理
    q_start = 2 + H * W
    Q = int(input_data[q_start])
    q_start += 1

    out = []
    for k in range(Q):
        r = int(input_data[q_start + 2 * k]) - 1
        c = int(input_data[q_start + 2 * k + 1]) - 1
        out.append(str(dist[r * W + c]))

    print("\n".join(out))


if __name__ == "__main__":
    main()

---

This editorial was generated by gemini-3.5-flash-high.