Cho ma trận 2D: 0 (trống), 1 (người), 2 (lửa), 3 (tường). Mỗi lượt: người đi trước (4 hướng), sau đó lửa lan 4 hướng (không qua tường). Kiểm tra người có thể đến (0,0) hoặc (R-1,C-1) không. Nếu người và lửa đến cùng lúc một ô, người vẫn sống.
Ví dụ ma trận 3x3: người ở (1,2), lửa ở (2,2) → True (đi đến (0,0)).
Giải pháp
BFS đa nguồn tính khoảng cách ngắn nhất:
- bfs(queue): trả về dict khoảng cách từ các nguồn trong queue
- Chạy BFS từ tất cả vị trí lửa → dist_fire
- Chạy BFS từ vị trí người → dist_person
- Kiểm tra (0,0) và (R-1,C-1): nếu dist_fire >= dist_person → True
- Dùng INF cho ô không thể đến
Ví dụ minh họa
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))
Đầu vào
[[0, 0, 0], [0, 0, 1], [0, 0, 2]]
Đầu ra
True