概要

この問題は、グリッド状の遺跡が外側から徐々に侵食されていくシミュレーションにおいて、各マスが完全に崩壊するステップ数を求める問題です。

一見すると毎ステップの状況を愚直にシミュレーションする必要があるように見えますが、グリッドをグラフとみなすことで、複数始点のダイクストラ法（最短経路問題）に帰着して高速に解くことができます。

---

考察

1. 愚直なシミュレーションの限界

各ステップで「風雨にさらされているマスの耐久値を \(1\) 減らす」という操作を愚直に行うとどうなるでしょうか。 マスの耐久値 \(C_{i,j}\) は最大で \(10^9\) に達するため、すべてのブロックが崩壊するまでには最大で \(10^9 \times (H+W)\) 程度のステップ数がかかる可能性があります。毎ステップの処理に \(O(HW)\) かかるとすると、全体の計算量は膨大になり、実行時間制限（TLE）に間に合いません。

したがって、ステップを \(1\) ずつ進めるのではなく、各マスが崩壊するステップ数を直接計算する方法を考える必要があります。

2. 崩壊するタイミングの規則性

ある内側のマス \(u\) が崩壊するプロセスを考えてみましょう。 マス \(u\) の耐久値の減少が始まるのは、上下左右に隣接するマスのうち、少なくとも \(1\) つが崩壊した瞬間です。

隣接するマス \(v\) が崩壊するステップ数を \(T[v]\) とします。 マス \(u\) が風雨にさらされ始めるのは、隣接するマスのうち「最も早く崩壊したマス」が崩壊したステップの直後です。つまり、さらされ始めるステップは以下のようになります。 $\(\min_{v \in \text{adj}(u)} T[v]\)$

そこからマス \(u\) 自身の耐久値 \(C[u]\) だけステップが経過すると、マス \(u\) も崩壊します。したがって、マス \(u\) が崩壊するステップ数 \(T[u]\) は次の式で表せます。 $\(T[u] = \min_{v \in \text{adj}(u)} T[v] + C[u]\)$

ただし、最初から風雨にさらされている外周のマス（\(1\) 行目、\(H\) 行目、\(1\) 列目、\(W\) 列目）については、最初から耐久値が減り始めるため、崩壊するステップ数は自身の耐久値そのものになります。 $\(T[u] = C[u] \quad (\text{外周のマス } u)\)$

3. 最短経路問題への帰着

上記の式をよく見ると、グラフの最短経路問題におけるダイクストラ法の更新式と全く同じ形をしていることが分かります。

• スタート地点: グリッドの外周にあるすべてのマス
• 初期コスト: 外周のマス \(u\) の初期コストは \(C[u]\)
• 移動コスト: マス \(v\) から隣接するマス \(u\) へ移動する際のコストは、移動先の耐久値 \(C[u]\)

この設定のもとで、外周のマスを同時に始点とした「複数始点ダイクストラ法」を実行すれば、すべてのマスについて崩壊するステップ数 \(T[i][j]\) を一挙に求めることができます。

---

アルゴリズム

複数始点ダイクストラ法を用いて、以下の手順で解を求めます。

1. 初期化:

   • 各マス \((i, j)\) が崩壊するステップ数を記録する配列 \(T[i][j]\) を作成し、十分大きな値（\(\infty\)）で初期化します。
   • 優先度付きキュー（最小ヒープ） pq を用意します。キューの要素は {コスト, {行, 列}} のペアです。

2. 始点の追加:

   • グリッドの外周にあるすべてのマス \((i, j)\) について、\(T[i][j] = C[i][j]\) とし、キューに {T[i][j], {i, j}} を追加します。

3. ダイクストラ法の実行:

   • キューが空になるまで以下を繰り返します。
     1. キューから最もコスト（崩壊ステップ数）が小さい要素 (dist, (r, c)) を取り出します。
     2. もし dist > T[r][c] であれば、すでに最短経路が確定しているため、この要素は無視して次のループに進みます（枝刈り）。
     3. マス \((r, c)\) の上下左右に隣接する各マス \((nr, nc)\) について、以下の更新を試みます。
        • もし \(T[nr][nc] > T[r][c] + C[nr][nc]\) ならば、
        • \(T[nr][nc] = T[r][c] + C[nr][nc]\) と更新し、キューに {T[nr][nc], {nr, nc}} を追加します。

4. クエリへの回答:

   • 各クエリで指定されたマス \((R_k, K_k)\) に対して、事前に計算した \(T[R_k-1][K_k-1]\) の値を \(O(1)\) で出力します。

---

計算量

時間計算量

• ダイクストラ法: グリッドのマス数（頂点数）を \(V = H \times W\)、隣接するマス間のつながり（辺の数）を \(E \approx 4V\) とします。 優先度付きキューを用いたダイクストラ法の時間計算量は \(O((V + E) \log V)\) です。 \(V = H \times W\) を代入すると、ダイクストラ法の部分は \(O(HW \log(HW))\) となります。
• クエリ処理: \(Q\) 個のクエリに対して、それぞれ \(O(1)\) で回答できるため、全体で \(O(Q)\) です。

したがって、全体の時間計算量は \(O(HW \log(HW) + Q)\) となり、制約下（\(H, W \le 500\), \(Q \le 10^5\)）で実行時間制限に十分間に合います。

空間計算量

• グリッドの耐久値 \(C\)、および各マスの崩壊ステップ数 \(T\) を保持するために \(O(HW)\) のメモリを使用します。
• 優先度付きキューに格納される要素数は最大でも \(O(HW)\) です。

したがって、空間計算量は \(O(HW)\) となり、メモリ制限に対しても非常に安全です。

---

実装のポイント

• データ型の選択: 耐久値 \(C_{i,j}\) は最大で \(10^9\) であり、崩壊ステップ数 \(T[i][j]\) は最大で \(10^9 \times (H \times W)\) 程度まで大きくなる可能性があります。 C++における通常の 32 ビット整数型（int）ではオーバーフローしてしまうため、ステップ数の計算や配列 \(T\) の要素、および無限大を表す定数 INF には 64 ビット整数型（long long） を使用する必要があります。

• 0-indexed への変換: 問題文の入力は 1-indexed（1から始まるインデックス）で与えられますが、プログラム内では 0-indexed（0から始まるインデックス）に変換して処理を行うと、配列のアクセスがスムーズになります。クエリの入力を受け取った際に r-1, k-1 とするのを忘れないようにしましょう。

  ソースコード

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

---

この解説は gemini-3.5-flash-high によって生成されました。