用Python检查人可以到达左上角或右下角的单元格的程序，以免发生火灾

假设我们有一个2D矩阵，其中包含几个不同的值，如下所示-

• 空单元为0

• 一个人1

• 2火

• 3墙

现在假设只有一个人，并且火势每一个方向都在四个方向（向上，向下，向左和向右）扩展，但是火不能穿过墙壁扩展。我们必须检查该人是否可以移动到左上角或右下角或矩阵。我们必须谨记，在每个回合中，人先移动，然后火势扩大。如果此人与火同时进入任何一个目标牢房，那么他是安全的。因此，如果人走到牢房，然后火以相同的方向向同一牢房扩展，该人仍然可以生存。

所以，如果输入像

那么输出将为True，因为此人可以转到左上角。

为了解决这个问题，我们将遵循以下步骤-

• R：= A的行数，C：= A的列数

• 定义一个功能bfs()。这将需要排队

• dist：=包含键作为队列节点且所有值均为0的映射

• 当队列不为空时，执行

• 如果nei不在dist，则

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

• 在队列末尾插入nei

• node：=队列的左项，然后删除左项

• 对于节点的每个邻居nei，

• 返回dist

• 从主要方法中执行以下操作-

• fire_que：=双头队列

• person_que：=双头队列

• 对于每个行索引r和行A，执行

• 如果v与1相同，则

• 否则，当v与2相同时，则

• 在person_que的末尾插入对(r,c)

• 在fire_que的末尾插入(r,c)对

• dist_fire：= bfs(fire_que)

• 对于行中的每个列索引c和值v，执行

• dist_person：= bfs(person_que)

• 对于(0,0)，（R − 1，C − 1）中的每个位置

• 返回True

• 如果（dist_fire [place]如果不存在，则INF）> =（dist_person [place]如果不存在，则2 * INF），然后

• 返回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