Giả sử chúng ta có một ma trận 2D với vài giá trị khác nhau như bên dưới -
-
0 cho ô trống
-
1 cho một người
-
2 cho lửa
-
3 cho một bức tường
Bây giờ giả sử chỉ có một người và trong mỗi lượt ngọn lửa sẽ mở rộng theo cả bốn hướng (lên, xuống, trái và phải) nhưng lửa không thể mở rộng qua các bức tường. Chúng ta phải kiểm tra xem người đó có thể di chuyển đến góc trên bên trái hoặc góc dưới bên phải hoặc ma trận hay không. Chúng ta phải ghi nhớ rằng trong mỗi lượt, người di chuyển trước, sau đó lửa mở rộng. Nếu người đó đến được bất kỳ ô nào trong số các ô mục tiêu cùng thời điểm với ngọn lửa, thì người đó sẽ an toàn. Vì vậy, nếu một người đi đến phòng giam và sau đó ngọn lửa bùng phát cùng một lượt đến cùng một ô, người đó vẫn sống sót.
Vì vậy, nếu đầu vào giống như
| 0 | 0 | 0 |
| 0 | 0 | 1 |
| 0 | 0 | 2 |
thì đầu ra sẽ là True, vì người đó có thể đi đến góc trên cùng bên trái.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
R:=số hàng của A, C:=số cột của A
-
Định nghĩa một hàm bfs (). Điều này sẽ mất hàng đợi
-
dist:=một bản đồ chứa khóa là nút của hàng đợi và tất cả các giá trị đều bằng 0
-
trong khi hàng đợi không trống, thực hiện
-
node:=mục bên trái của hàng đợi, sau đó xóa mục bên trái
-
đối với mỗi nei lân cận của nút, thực hiện
-
nếu nei không có trong dist, thì
-
dist [nei]:=dist [node] + 1
-
chèn nei vào cuối hàng đợi
-
-
-
-
trả lại bản phân phối
-
Từ phương thức chính, hãy làm như sau -
-
fire_que:=một hàng đợi kết thúc kép
-
person_que:=một hàng đợi kết thúc kép
-
đối với mỗi chỉ mục hàng r và hàng A, thực hiện
-
đối với mỗi chỉ số cột c và giá trị v trong hàng, thực hiện
-
nếu v giống 1 thì
-
chèn cặp (r, c) vào cuối person_que
-
-
ngược lại khi v giống 2 thì
-
chèn cặp (r, c) vào cuối fire_que
-
dist_fire:=bfs (fire_que)
-
-
-
-
dist_woman:=bfs (person_que)
-
cho mỗi vị trí trong (0, 0), (R - 1, C - 1), thực hiện
-
if (dist_fire [place] nếu không tồn tại thì INF)> =(dist_woman [place] nếu không tồn tại thì 2 * INF), sau đó
-
trả về True
-
-
-
trả về Sai
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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