概要

各マスのブロックが崩壊するステップを求める問題です。
重要なのは、崩壊時刻を「外周からそのマスまで進むときに通るマスの耐久値の和の最小値」として考えられる点です。

考察

あるマス \(v\) の崩壊するステップを \(T(v)\) とします。

まず、外周のマスは最初から風雨にさらされています。
そのため、耐久値が \(C_v\) の外周マスは、ステップ \(1\) から毎ステップ \(1\) ずつ減り、ちょうどステップ \(C_v\) で崩壊します。

つまり、外周マスについては

\[ T(v) = C_v \]

です。

次に、内側のマスを考えます。

ある隣接マス \(u\) がステップ \(T(u)\) で崩壊したとします。
すると、マス \(v\) は次のステップ \(T(u)+1\) から風雨にさらされます。

耐久値が \(C_v\) なら、そこから \(C_v\) 回減少して崩壊するので、崩壊ステップは

\[ T(u) + C_v \]

になります。

したがって、マス \(v\) は隣接マスのうち最も早く崩壊するものから侵食を受けるので、

\[ T(v) = C_v + \min_{u \in \text{隣接マス}} T(u) \]

と表せます。

これは見方を変えると、

• 外周マスをスタート地点とする
• マスに入るコストをそのマスの耐久値 \(C_{i,j}\) とする
• 各マスへの最短距離を求める

という問題になります。

つまり、マス \(v\) の崩壊ステップは

\[ T(v) = \min_{\text{外周から } v \text{ への経路}} \sum_{\text{経路上のマス } x} C_x \]

です。

例えば、ある外周マスから耐久値 \(3, 5, 2\) のマスを順に通って目的のマスに到達するなら、その目的マスは

\[ 3 + 5 + 2 = 10 \]

ステップ目に崩壊します。

素朴なシミュレーションでは間に合わない

各ステップごとに風雨にさらされているマスを調べて耐久値を減らす、というシミュレーションをすると、耐久値が最大 \(10^9\) なので非常に時間がかかります。

また、崩壊ステップの最大値は経路上の耐久値の和になるため、最大で

\[ 500 \times 500 \times 10^9 \]

程度になる可能性があります。
ステップを 1 つずつ進める方法では到底間に合いません。

そこで、これは重み付きグラフの最短路問題として考え、ダイクストラ法で解きます。

アルゴリズム

グリッドの各マスを頂点とみなします。

辺は上下左右に隣接するマス同士に張ります。
あるマス \(v\) から隣接マス \(u\) へ進むときのコストは、移動先である \(u\) の耐久値 \(C_u\) です。

外周マスは最初から風雨にさらされているので、初期距離をそのマスの耐久値にします。

手順は以下の通りです。

1. 各マスの崩壊ステップ dist を無限大で初期化する
2. 外周マスについて、dist = C として優先度付きキューに入れる
3. ダイクストラ法を行う
   • 崩壊ステップが小さいマスから取り出す
   • そのマスに隣接するマスについて、次の値で更新する

\[ \text{新しい候補} = \text{現在のマスの崩壊ステップ} + \text{隣接マスの耐久値} \]

1. クエリで指定されたマスの dist を出力する

この dist が、そのマスの崩壊するステップ番号になります。

計算量

\(N = H \times W\) とします。

グリッドの辺の数は高々 \(4N\) 程度です。
ダイクストラ法を用いるので、

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

です。

実装のポイント

• マス \((r, c)\) は idx = r * W + c として 1 次元に変換しています。

• 優先度付きキューには (崩壊ステップ, マス番号) を入れます。

• ダイクストラ法では、古い情報がキューに残ることがあるため、取り出した値が現在の dist と一致しない場合は無視します。

• 隣接マスを更新するときは、+1 ではなく + C[隣接マス] します。

  • 隣のマスが崩壊した次のステップから侵食が始まり、耐久値ぶんだけステップが必要だからです。

• コードでは、クエリに現れる内側のマスがすべて確定した時点でダイクストラ法を打ち切る最適化も入っています。外周マスの答えは最初から C で確定しています。

  ソースコード

import sys
from heapq import heappush, heappop, heapify

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    p = 0

    H = data[p]
    W = data[p + 1]
    p += 2

    N = H * W
    C = data[p:p + N]
    p += N

    Q = data[p]
    p += 1

    queries = [0] * Q
    target = bytearray(N)
    remain = 0

    bottom = H - 1
    right = W - 1

    for qi in range(Q):
        r = data[p] - 1
        c = data[p + 1] - 1
        p += 2

        idx = r * W + c
        queries[qi] = idx

        if r != 0 and r != bottom and c != 0 and c != right:
            if target[idx] == 0:
                target[idx] = 1
                remain += 1

    del data

    if remain == 0:
        sys.stdout.write("\n".join([str(C[idx]) for idx in queries]))
        return

    INF = 10 ** 18
    dist = [INF] * N
    heap = []

    # top row
    for j in range(W):
        v = C[j]
        dist[j] = v
        heap.append((v, j))

    # bottom row
    base = N - W
    for j in range(base, N):
        v = C[j]
        dist[j] = v
        heap.append((v, j))

    # left and right columns excluding corners
    last_col = W - 1
    for idx in range(W, base, W):
        v = C[idx]
        dist[idx] = v
        heap.append((v, idx))

        idx2 = idx + last_col
        v = C[idx2]
        dist[idx2] = v
        heap.append((v, idx2))

    heapify(heap)

    pop = heappop
    push = heappush
    c_arr = C
    d_arr = dist
    tgt = target
    width = W
    total = N
    lower_limit = N - W
    rem = remain

    while heap:
        d, v = pop(heap)
        if d != d_arr[v]:
            continue

        if tgt[v]:
            tgt[v] = 0
            rem -= 1
            if rem == 0:
                break

        if v >= width:
            u = v - width
            nd = d + c_arr[u]
            if nd < d_arr[u]:
                d_arr[u] = nd
                push(heap, (nd, u))

        if v < lower_limit:
            u = v + width
            nd = d + c_arr[u]
            if nd < d_arr[u]:
                d_arr[u] = nd
                push(heap, (nd, u))

        col = v % width

        if col:
            u = v - 1
            nd = d + c_arr[u]
            if nd < d_arr[u]:
                d_arr[u] = nd
                push(heap, (nd, u))

        if col != last_col:
            u = v + 1
            nd = d + c_arr[u]
            if nd < d_arr[u]:
                d_arr[u] = nd
                push(heap, (nd, u))

    sys.stdout.write("\n".join([str(dist[idx]) for idx in queries]))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。