Summary

In this problem, we simulate a grid-like ruin being gradually eroded from the outside, and we need to find the number of steps it takes for each cell to completely collapse.

At first glance, it might seem necessary to simulate the process step-by-step. However, by treating the grid as a graph, we can reduce this to a multi-source Dijkstra’s algorithm (shortest path problem) and solve it efficiently.

---

Analysis

1. Limitations of Naive Simulation

What happens if we perform a naive simulation where, at each step, we “decrement the durability of cells exposed to the elements by \(1\)”? The durability of a cell \(C_{i,j}\) can be up to \(10^9\), so it could take up to \(10^9 \times (H+W)\) steps for all blocks to collapse in the worst case. If each step takes \(O(HW)\) time, the total time complexity becomes enormous, leading to a Time Limit Exceeded (TLE) error.

Therefore, instead of advancing the simulation step-by-step, we need a way to directly calculate the step at which each cell collapses.

2. Regularity of the Collapse Timing

Let us consider the process of an internal cell \(u\) collapsing. The durability of cell \(u\) starts decreasing at the exact moment at least one of its adjacent cells (up, down, left, or right) collapses.

Let \(T[v]\) be the step at which an adjacent cell \(v\) collapses. Cell \(u\) starts being exposed to the elements immediately after the “earliest collapsing adjacent cell” collapses. Thus, the step at which it starts being exposed is: $\(\min_{v \in \text{adj}(u)} T[v]\)$

From that moment, it takes \(C[u]\) steps (its own durability) for cell \(u\) to collapse. Therefore, the step \(T[u]\) at which cell \(u\) collapses can be expressed as: $\(T[u] = \min_{v \in \text{adj}(u)} T[v] + C[u]\)$

However, for the perimeter cells (row \(1\), row \(H\), column \(1\), column \(W\)) which are exposed to the elements from the very beginning, their durability starts decreasing immediately. Thus, their collapse step is simply their own durability: $\(T[u] = C[u] \quad (\text{perimeter cell } u)\)$

3. Reduction to the Shortest Path Problem

If you look closely at the formula above, you will notice that it has the exact same form as the relaxation formula of Dijkstra’s algorithm in the shortest path problem.

• Starting points: All cells on the perimeter of the grid.
• Initial cost: The initial cost of a perimeter cell \(u\) is \(C[u]\).
• Transition cost: The cost to move from cell \(v\) to an adjacent cell \(u\) is the durability of the destination, \(C[u]\).

Under this setup, if we run a “multi-source Dijkstra’s algorithm” starting from all perimeter cells simultaneously, we can find the collapse step \(T[i][j]\) for all cells at once.

---

Algorithm

We can find the solution using multi-source Dijkstra’s algorithm with the following steps:

1. Initialization:

   • Create an array \(T[i][j]\) to record the step at which each cell \((i, j)\) collapses, and initialize it with a sufficiently large value (\(\infty\)).
   • Prepare a priority queue (min-heap) pq. The elements of the queue are pairs of the form {cost, {row, col}}.

2. Adding Starting Points:

   • For all cells \((i, j)\) on the perimeter of the grid, set \(T[i][j] = C[i][j]\) and add {T[i][j], {i, j}} to the queue.

3. Running Dijkstra’s Algorithm:

   • Repeat the following until the queue is empty:
     1. Extract the element (dist, (r, c)) with the smallest cost (collapse step) from the queue.
     2. If dist > T[r][c], the shortest path to this cell has already been determined, so ignore this element and proceed to the next iteration (pruning).
     3. For each adjacent cell \((nr, nc)\) (up, down, left, right) of cell \((r, c)\), attempt the following update:
        • If \(T[nr][nc] > T[r][c] + C[nr][nc]\):
        • Update \(T[nr][nc] = T[r][c] + C[nr][nc]\) and add {T[nr][nc], {nr, nc}} to the queue.

4. Answering Queries:

   • For each query specifying cell \((R_k, K_k)\), output the precomputed value \(T[R_k-1][K_k-1]\) in \(O(1)\) time.

---

Complexity

Time Complexity

• Dijkstra’s Algorithm: Let the number of grid cells (vertices) be \(V = H \times W\), and the connections between adjacent cells (edges) be \(E \approx 4V\). The time complexity of Dijkstra’s algorithm using a priority queue is \(O((V + E) \log V)\). Substituting \(V = H \times W\), the Dijkstra phase takes \(O(HW \log(HW))\) time.
• Query Processing: Since each of the \(Q\) queries can be answered in \(O(1)\) time, the total time for queries is \(O(Q)\).

Thus, the overall time complexity is \(O(HW \log(HW) + Q)\), which is well within the execution time limit under the constraints (\(H, W \le 500\), \(Q \le 10^5\)).

Space Complexity

• We use \(O(HW)\) memory to store the durability grid \(C\) and the collapse steps \(T\) for each cell.
• The number of elements stored in the priority queue is at most \(O(HW)\).

Thus, the space complexity is \(O(HW)\), which is highly safe with respect to the memory limit.

---

Implementation Details

• Choosing Data Types: The durability \(C_{i,j}\) is at most \(10^9\), and the collapse step \(T[i][j]\) can grow up to approximately \(10^9 \times (H \times W)\). Using a standard 32-bit integer type (int in C++) will cause an overflow. Therefore, you must use a 64-bit integer type (long long) for the step calculations, the elements of array \(T\), and the constant INF representing infinity.

• 0-indexed Conversion: The input in the problem description is given as 1-indexed. Converting it to 0-indexed in your program will make array accesses smoother. Don’t forget to use r-1 and k-1 when reading the query inputs.

  Source Code

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

const long long INF = 1e18;

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int H, W;
    if (!(cin >> H >> W)) return 0;

    vector<vector<long long>> C(H, vector<long long>(W));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> C[i][j];
        }
    }

    vector<vector<long long>> T(H, vector<long long>(W, INF));
    // {最短距離, {行, 列}}
    using P = pair<long long, pair<int, int>>;
    priority_queue<P, vector<P>, greater<P>> pq;

    // 初期状態として、グリッドの外周にあるマス（最初から風雨にさらされているマス）をキューに登録
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (i == 0 || i == H - 1 || j == 0 || j == W - 1) {
                T[i][j] = C[i][j];
                pq.push({T[i][j], {i, j}});
            }
        }
    }

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    // ダイクストラ法による最短経路（崩壊ステップ）の計算
    while (!pq.empty()) {
        auto [dist, coord] = pq.top();
        pq.pop();
        int r = coord.first;
        int c = coord.second;

        if (dist > T[r][c]) continue;

        for (int d = 0; d < 4; ++d) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
                if (T[nr][nc] > dist + C[nr][nc]) {
                    T[nr][nc] = dist + C[nr][nc];
                    pq.push({T[nr][nc], {nr, nc}});
                }
            }
        }
    }

    int Q;
    if (cin >> Q) {
        for (int q = 0; q < Q; ++q) {
            int r, k;
            cin >> r >> k;
            --r; --k; // 0-indexed に変換
            cout << T[r][k] << "\n";
        }
    }

    return 0;
}

---

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