概要

各マスの石ブロックが崩壊するステップ番号を求める問題です。これは「グリッドの外側」を仮想的な始点とした Dijkstra 法（最短経路問題） に帰着できます。

考察

崩壊するタイミングを式で表す

まず、あるマスが「いつ崩壊するか」を考えます。重要な観察は次の 2 点です。

• 一度風雨にさらされたマスは、その後ずっとさらされ続ける 風雨にさらされる原因は「隣が空きマス（崩壊済み）または外側」であることですが、崩壊済みのマスが復活することはないため、一度さらされたマスは崩壊するまで毎ステップ耐久値が \(1\) ずつ減り続けます。

• したがって、あるマスの崩壊ステップは 「最初に風雨にさらされ始めたステップ」＋「耐久値」 で決まります。

これを具体的に式にします。マス \((i,j)\) の崩壊ステップを \(\mathrm{dist}[i][j]\) とおきます。

外周のマス（\(1\) 行目・\(H\) 行目・\(1\) 列目・\(W\) 列目）は、初期状態から外側に接しているため、ステップ \(1\) から耐久値が減り始めます。よって耐久値 \(C_{i,j}\) の分だけステップが必要で、

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

内側のマスは、隣接マスのいずれかが崩壊して初めて風雨にさらされます。隣がステップ \(t\) の終わりに崩壊すると、問題文より「新たにさらされたブロックは次のステップの処理 1 から減り始める」ため、ステップ \(t+1\) から減少が始まり、\(C_{i,j}\) ステップ後、つまりステップ \(t + C_{i,j}\) で崩壊します。最も早く崩壊する隣を選べばよいので、

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

漸化式の意味

外側を「崩壊ステップ \(0\) の仮想ノード」と考えると、外周マスの式も

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

と統一的に書けます。つまりすべてのマスについて

\[ \mathrm{dist}[v] = \min_{u \text{ は } v \text{ の隣}} \mathrm{dist}[u] + C_v \]

が成り立ちます。これは「あるマスに入るときにそのマスの耐久値 \(C_v\) を支払う」と考えると、外側からの最短経路（コストの合計が最小の経路） を求めることそのものです。

素朴な方法ではなぜダメか

耐久値は最大 \(10^9\) なので、ステップを 1 つずつ進めるシミュレーションは \(10^9\) 回以上のステップが必要になり、まったく間に合いません。上記の最短経路の定式化を使うことで、シミュレーションせずに直接答えを計算できます。

アルゴリズム

上記の漸化式は、辺のコストが非負（\(C_v \ge 1\)）なので Dijkstra 法 で解けます。

1. 外側を始点（距離 \(0\)）とみなす。すなわち外周のマス \((i,j)\) を初期距離 \(C_{i,j}\) として優先度付きキューに入れる。
2. 距離が最小のマスを取り出し、隣接マス \((nx,ny)\) に対して $\( nd = \mathrm{dist}[x][y] + C_{nx,ny} \)$ で緩和を行う。
3. これを繰り返すと、全マスの崩壊ステップ \(\mathrm{dist}\) が確定する。

各クエリは確定した \(\mathrm{dist}\) を \(O(1)\) で参照するだけです。

計算量

マス数を \(N = HW\) とします。

• 時間計算量: \(O(HW \log(HW) + Q)\)
• 空間計算量: \(O(HW)\)

\(H, W \le 500\) なので \(HW \le 250000\) となり、十分高速です。

実装のポイント

• オーバーフローに注意：耐久値は最大 \(10^9\)、最短経路上のマス数は最大で \(\min(H,W)/2\) 程度（およそ \(250\)）になり得るため、距離の合計は \(10^9 \times 250 \approx 2.5\times 10^{11}\) に達します。int では収まらないので long long を使います。

• 初期化：外周のマスをすべて始点として優先度付きキューに入れます。greater<> を使って「距離が小さい順」に取り出す最小ヒープとして使います。

• 取り出し時のチェック：if(d > dist[x][y]) continue; で、すでに更新済みの古いエントリをスキップします。これにより同じマスを何度も処理するのを防ぎます。

• クエリのマスは \(1\)-indexed で与えられるので、配列アクセス時に \(-1\) して \(0\)-indexed に変換します。

  ソースコード

#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;
}

---

この解説は claude4.8opus-high によって生成されました。