資料結構
網路
關係資料庫管理系統(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 次瀏覽
