用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