Summary

This problem asks us to find the step number at which the stone block in each cell collapses. This can be modeled as Dijkstra’s algorithm (shortest path problem) with the “outside of the grid” as a virtual starting point.

Analysis

Expressing the Collapse Timing as a Formula

First, let’s consider when a cell collapses. There are two key observations:

• Once a cell is exposed to the elements, it remains exposed forever. The cause of exposure is having an adjacent cell that is either empty (already collapsed) or outside the grid. Since collapsed cells never recover, once a cell is exposed, its durability continues to decrease by \(1\) in each step until it collapses.

• Therefore, the step in which a cell collapses is determined by: “the step when it first became exposed” + “its durability”.

Let’s formulate this. Let \(\mathrm{dist}[i][j]\) be the step when cell \((i,j)\) collapses.

Boundary cells (the \(1\)-st row, \(H\)-th row, \(1\)-st column, and \(W\)-th column) are adjacent to the outside from the initial state, so their durability starts decreasing from step \(1\). Therefore, they require steps equal to their durability \(C_{i,j}\):

\[ \mathrm{dist}[i][j] = C_{i,j} \]

Inner cells are exposed to the elements only after at least one of their adjacent cells collapses. If an adjacent cell collapses at the end of step \(t\), according to the problem statement, “newly exposed blocks start decreasing from process 1 of the next step.” Thus, the decrease starts from step \(t+1\), and the cell collapses after \(C_{i,j}\) steps, i.e., at step \(t + C_{i,j}\). Since we should choose the adjacent cell that collapses earliest, we have:

\[ \mathrm{dist}[i][j] = \Bigl(\min_{(x,y) \text{ adjacent to } (i,j)} \mathrm{dist}[x][y]\Bigr) + C_{i,j} \]

Meaning of the Recurrence Relation

If we consider the outside as a “virtual node with collapse step \(0\),” the formula for the boundary cells can also be written uniformly as:

\[ \mathrm{dist}[i][j] = 0 + C_{i,j} \]

Thus, for all cells, we have:

\[ \mathrm{dist}[v] = \min_{u \text{ adjacent to } v} \mathrm{dist}[u] + C_v \]

If we think of this as “paying a cost of \(C_v\) when entering a cell,” this is exactly equivalent to finding the shortest path from the outside (the path with the minimum total cost).

Why a Naive Approach Fails

Since the durability can be up to \(10^9\), a simulation that advances step-by-step would require \(10^9\) or more steps, which will easily time out. By using the shortest path formulation above, we can calculate the answer directly without simulating the process.

Algorithm

Since the edge costs are non-negative (\(C_v \ge 1\)), the recurrence relation above can be solved using Dijkstra’s algorithm.

1. Treat the outside as the starting point (distance \(0\)). That is, push the boundary cells \((i,j)\) into a priority queue with an initial distance of \(C_{i,j}\).
2. Pop the cell with the minimum distance, and for each adjacent cell \((nx,ny)\), perform relaxation as follows: $\( nd = \mathrm{dist}[x][y] + C_{nx,ny} \)$
3. By repeating this process, the collapse step \(\mathrm{dist}\) for all cells will be determined.

Each query can then be answered in \(O(1)\) time by simply referencing the determined \(\mathrm{dist}\).

Complexity

Let \(N = HW\) be the number of cells.

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

Since \(H, W \le 500\), we have \(HW \le 250000\), which is fast enough.

Implementation Details

• Beware of Overflow: The durability can be up to \(10^9\), and the number of cells on the shortest path can be up to about \(\min(H,W)/2\) (roughly \(250\)). Therefore, the total distance can reach \(10^9 \times 250 \approx 2.5\times 10^{11}\). This exceeds the range of a standard 32-bit int, so use long long (or 64-bit integers).

• Initialization: Push all boundary cells into the priority queue as starting points. Use a min-heap (e.g., using greater<> in C++) to pop elements in ascending order of distance.

• Check upon Popping: Use if(d > dist[x][y]) continue; to skip outdated entries that have already been updated. This prevents processing the same cell multiple times.

• Since the query cells are given in \(1\)-based indexing, convert them to \(0\)-based indexing by subtracting \(1\) when accessing the array.

  Source Code

#include <bits/stdc++.h>
using namespace std;
int main(){
    int H,W;
    scanf("%d %d",&H,&W);
    vector<vector<long long>> C(H, vector<long long>(W));
    for(int i=0;i<H;i++)for(int j=0;j<W;j++) scanf("%lld",&C[i][j]);
    const long long INF = LLONG_MAX;
    vector<vector<long long>> dist(H, vector<long long>(W, INF));
    priority_queue<tuple<long long,int,int>, vector<tuple<long long,int,int>>, greater<>> 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){
            if(C[i][j] < dist[i][j]){
                dist[i][j]=C[i][j];
                pq.push({dist[i][j], i, j});
            }
        }
    }
    int dx[]={1,-1,0,0}, dy[]={0,0,1,-1};
    while(!pq.empty()){
        auto [d,x,y]=pq.top(); pq.pop();
        if(d>dist[x][y]) continue;
        for(int k=0;k<4;k++){
            int nx=x+dx[k], ny=y+dy[k];
            if(nx<0||nx>=H||ny<0||ny>=W) continue;
            long long nd = d + C[nx][ny];
            if(nd < dist[nx][ny]){
                dist[nx][ny]=nd;
                pq.push({nd,nx,ny});
            }
        }
    }
    int Q; scanf("%d",&Q);
    while(Q--){
        int r,k; scanf("%d %d",&r,&k);
        printf("%lld\n", dist[r-1][k-1]);
    }
    return 0;
}

---

This editorial was generated by claude4.8opus-high.