在Python中编写程序以检查人员是否可以到达顶部左侧或底部右侧单元格而避免火灾。
假设我们有一个2D矩阵,其中有几个不同的值,如下所示-
- 0表示空单元格
-
1表示人
-
2表示火
-
3表示墙壁
现在假设只有一个人,并且在每次回合中,火向四个方向(上、下、左、右)扩展,但火不能穿过墙壁。我们必须检查人是否能够移动到左上角或右下角或矩阵。我们必须记住,在每次回合中,人首先移动,然后火扩展。如果人在与火同时到达任何目标单元格,则他是安全的。因此,如果人到达单元格,然后在同一回合中火扩展到同一单元格,则人仍然可以生存。
因此,如果输入如下所示:
0 | 0 | 0 |
---|---|---|
0 | 0 | 1 |
0 | 0 | 2 |
那么输出将为True,因为人可以走到左上角。
要解决这个问题,我们将按照以下步骤进行 −
- R:= A的行数,C:= A的列数
-
定义一个函数bfs()。这将花费队列
-
dist: =包含队列节点的所有值为0的映射的映射
-
while队列不为空,做
- node:=队列的左侧项目,然后删除左侧项目
-
对于节点的每个邻居nei,执行以下操作
- 如果nei不在dist中,则
-
dist [nei]:= dist [node] +1
-
在队列的末尾插入nei
-
返回dist
-
从主方法执行以下操作−
-
火队:=双端队列
-
人队:=双端队列
-
对于A中的每个行索引r和行,执行以下操作
- 对于列索引c和行中的值v,执行以下操作
- 如果v与1相同,则
-
在人队的末尾插入对(r,c)进行配对
-
否则当v等于2时,则
-
在fire_que的末尾插入对(r,c)进行配对
-
dist_fire:= bfs(fire_que)
- 对于列索引c和行中的值v,执行以下操作
-
dist_person:= bfs(person_que)
-
对于(0,0)、(R-1,C-1)中的每个位置,执行以下操作
- 如果(dist_fire [place]不存在,则INF)> =(dist_person [place]不存在,则2 * INF) ,则
- 返回True
- 如果(dist_fire [place]不存在,则INF)> =(dist_person [place]不存在,则2 * INF) ,则
- 返回False
让我们看以下实现以更好地理解−
更多Python相关文章,请阅读: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