Pythonで解く!人が火災を避けて左上または右下のセルに到達できるかを判定するプログラム

問題の概要

以下のように、いくつかの異なる値を持つ2次元マトリックス(行列)を想定します。

• 0:空きセル

• 1:人

• 2:火災

• 3:壁

ここで、マトリックス上には人が1人だけ存在し、毎ターン火災は上下左右の4方向へ広がっていきます。ただし、火災は壁を越えて広がることはできません。私たちの課題は、人がマトリックスの左上隅または右下隅のいずれかに到達できるかどうかを判定することです。

判定の際に押さえておくべきルールは以下の通りです。

• 各ターンでは、人が先に移動し、その後で火災が広がります。

• 人が目標セルに到着したのと同じターンで火災がそのセルに広がっても、人は安全です。つまり、人がセルに入った直後に同じターン内で火が追いついても、人は生き残れます。

例えば、入力が以下のような場合を考えます。

この場合、出力は True になります。人は左上隅へ逃げることができるからです。

解決アプローチ:BFS(幅優先探索)の活用

この問題は、人と火災それぞれの最短到達ターン数をBFSで求め、目標セルでの到達時間を比較することで解けます。具体的な手順は以下の通りです。

• R := A の行数、C := A の列数とします。

• bfs() 関数を定義します。引数としてキューを受け取ります。

• dist := キュー内のノードをキーとし、すべての値を 0 としたマップを作成します。

• キューが空になるまで、以下を繰り返します。

  • node := キューの先頭要素を取り出して削除します。

  • node の各隣接セル nei について、以下を確認します。

    • nei が dist に存在しない場合:

      • dist[nei] := dist[node] + 1 とします。

      • nei をキューの末尾に追加します。

• dist を返します。

続いて、メイン処理では以下を実行します。

• fire_que := 火災用の両端キュー(deque)を作成します。

• person_que := 人用の両端キュー(deque)を作成します。

• A の各行インデックス r と各行 row に対して、以下を繰り返します。

  • 行内の各列インデックス c と値 v に対して、以下を判定します。

    • v が 1 の場合:(r, c) を person_que の末尾に追加します。

    • v が 2 の場合:(r, c) を fire_que の末尾に追加します。

• dist_fire := bfs(fire_que) で火災の拡散距離を計算します。

• dist_person := bfs(person_que) で人の移動距離を計算します。

• (0, 0) と (R − 1, C − 1) の各地点 place について、以下を判定します。

  • dist_fire[place](存在しない場合は INF)>= dist_person[place](存在しない場合は 2 * INF)であれば、True を返します。

• いずれの条件も満たさなければ、False を返します。

理解を深めるために、以下の実装例を見てみましょう。

サンプルコード(Python)

from collections import deque
class Solution:
    def solve(self, A):
        INF = int(1e9)
        R, C = len(A), len(A[0])
        def get_nei(r, c):
            for nr, nc in [[r - 1, c], [r, c - 1], [r + 1, c], [r, c + 1]]:
                if 0 <= nr < R and 0 <= nc < C and A[nr][nc] != 3:
                    yield nr, nc
        def bfs(queue):
            dist = {node: 0 for node in queue}
            while queue:
                node = queue.popleft()
                for nei in get_nei(*node):
                    if nei not in dist:
                        dist[nei] = dist[node] + 1
                        queue.append(nei)
            return dist
        fire_que = deque()
        person_que = deque()
        for r, row in enumerate(A):
            for c, v in enumerate(row):
                if v == 1:
                    person_que.append((r, c))
                elif v == 2:
                    fire_que.append((r, c))
        dist_fire = bfs(fire_que)
        dist_person = bfs(person_que)
        for place in ((0, 0), (R-1, C-1)):
            if dist_fire.get(place, INF) >= dist_person.get(place, 2 * INF):
                return True
        return False

ob = Solution()
matrix = [
    [0, 0, 0],
    [0, 0, 1],
    [0, 0, 2]
]
print(ob.solve(matrix))

入力

[[0, 0, 0], [0, 0, 1], [0, 0, 2]]

出力

True

まとめ

このアルゴリズムでは、人と火災それぞれについてBFSによる最短距離(ターン数)を事前に計算し、目標セルにおいて「人の到達ターン数 ≤ 火災の到達ターン数」であれば脱出成功と判定します。「人が先に動く」というルールにより、同時到着でも安全とみなせる点が大きなポイントです。壁(値3)は隣接セルの生成時に除外されるため、火災も人も壁を通過できません。計算量はグリッドのセル数に比例する O(R×C) 程度に収まり、効率的に動作します。