数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：检查一个人是否可以避开火灾到达左上角或右下角单元格
假设我们有一个二维矩阵，其中包含一些不同的值，如下所示：
0 表示空单元格
1 表示一个人
2 表示火
3 表示墙
现在假设只有一人，并且在每一轮中，火都向四个方向（上、下、左、右）蔓延，但火不能穿过墙壁。我们必须检查这个人是否可以移动到矩阵的左上角或右下角。我们必须记住，在每一轮中，人先移动，然后火蔓延。如果人在同一轮到达任何目标单元格的同时火也到达了，那么他就是安全的。所以如果人到达单元格，然后火在同一轮蔓延到同一单元格，这个人仍然幸存。
因此，如果输入如下所示：
| 0 | 0 | 0 |
| 0 | 0 | 1 |
| 0 | 0 | 2 |
则输出为 True，因为这个人可以到达左上角。
为了解决这个问题，我们将遵循以下步骤：
R := A 的行数，C := A 的列数
定义一个函数 bfs()。这将采用队列
dist := 一个映射，其键是队列的节点，所有值均为 0
当队列不为空时，执行
node := 队列的左侧项目，然后删除左侧项目
对于节点的每个邻居 nei，执行
如果 nei 不在 dist 中，则
dist[nei] := dist[node] + 1
将 nei 插入队列的末尾
返回 dist
从主方法执行以下操作：
fire_que := 一个双端队列
person_que := 一个双端队列
对于每一行索引 r 和行 A，执行
对于每一列索引 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) 中的每个位置，执行
如果 (如果不存在则为 INF) dist_fire[place] >= (如果不存在，则为 2 * INF) dist_person[place]，则
返回 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
92 次浏览
