人をチェックするプログラムは、Pythonで火災を回避するかどうかにかかわらず、左上または右下のセルに到達できます

以下のようないくつかの異なる値を持つ2D行列があるとします-

• 空のセルの場合は0

• 1人に1人

• 火の場合は2

• 壁の場合は3

ここで、人が1人だけで、各ターンで火が4方向すべて（上、下、左、右）に拡大するとしますが、火は壁を越えて拡大することはできません。人が左上隅、右下隅、またはマトリックスのいずれかに移動できるかどうかを確認する必要があります。各ターンで、人が最初に移動し、次に火が拡大することを覚えておく必要があります。人が火事と同時に標的細胞のいずれかに到達した場合、彼は安全です。したがって、人が独房に行き、同じ順番で同じ独房に火が広がった場合でも、その人は生き残ります。

したがって、入力が次のような場合

その場合、人は左上隅に移動できるため、出力はTrueになります。

これを解決するには、次の手順に従います-

• R：=Aの行数、C：=Aの列数

• 関数bfs（）を定義します。これはキューになります

• dist：=キューのノードとしてキーを含み、すべての値が0であるマップ

• キューが空でないときに、実行します

  • node：=キューの左側のアイテム、次に左側のアイテムを削除

  • ノードの隣接ネイごとに、実行します

    • neiが離れていない場合は、

      • dist [nei]：=dist [node] + 1

      • キューの最後にneiを挿入します

• 戻り距離

• メインの方法から、次のようにします-

• fire_que：=両端キュー

• person_que：=両端キュー

• 行インデックスrと行Aごとに、次のようにします

  • 行の各列インデックスcと値vについて、実行します

    • vが1と同じ場合、

      • person_queの最後にペア（r、c）を挿入します

    • それ以外の場合、vが2と同じ場合、

      • fire_queの最後にペア（r、c）を挿入します

      • dist_fire：=bfs（fire_que）

• dist_person：=bfs（person_que）

• （0、0）、（R − 1、C − 1）の各場所について、実行

  • if（dist_fire [place] if not presents then INF）> =（dist_person [place] if not presents then、2 * INF）、then

    • Trueを返す

• Falseを返す

理解を深めるために、次の実装を見てみましょう-

例

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