Giả sử chúng ta có một lưới, có 1 triệu hàng và 1 triệu cột, chúng ta cũng có một danh sách các ô bị chặn. Bây giờ chúng ta sẽ bắt đầu ở hình vuông nguồn và muốn đạt được hình vuông mục tiêu. Trong mỗi lần di chuyển, chúng ta có thể đi đến một ô vuông liền kề lên, xuống, trái, phải trong lưới không có trong danh sách ô bị chặn đã cho.
Chúng tôi phải kiểm tra xem liệu có thể đạt được mục tiêu thông qua một chuỗi các bước di chuyển hay không.
Vì vậy, nếu đầu vào giống như bị chặn =[[0,1], [1,0]], source =[0,0], target =[0,3], thì đầu ra sẽ là False
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
bị chặn:=tạo một tập hợp tất cả các ô bị chặn
-
Xác định một phương thức dfs (), phương thức này sẽ lấy x, y, target và saw
-
nếu (x, y) không nằm trong phạm vi lưới hoặc (x, y) bị chặn hoặc (x, y) được nhìn thấy thì
-
trả về false
-
-
-
thêm (x, y) vào đã thấy
-
nếu kích thước đã thấy> 20000 hoặc (x, y) là mục tiêu, thì
-
trả về true
-
-
trả về dfs (x + 1, y, target, saw) hoặc dfs (x-1, y, target, saw) hoặc dfs (x, y + 1, target, saw) hoặc dfs (x, y-1, target, đã thấy)
-
trả về dfs (nguồn [0], nguồn [1], đích, bộ trống) và dfs (đích [0], đích [1], nguồn, bộ trống)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution(object): def isEscapePossible(self, blocked, source, target): blocked = set(map(tuple, blocked)) def dfs(x, y, target, seen): if not (0 <= x < 10**6 and 0 <= y < 10**6) or (x, y) in blocked or (x, y) in seen: return False seen.add((x, y)) if len(seen) > 20000 or [x, y] == target: return True return dfs(x + 1, y, target, seen) or \ dfs(x - 1, y, target, seen) or \ dfs(x, y + 1, target, seen) or \ dfs(x, y - 1, target, seen) return dfs(source[0], source[1], target, set()) and dfs(target[0], target[1], source, set()) ob = Solution() print(ob.isEscapePossible([[0,1],[1,0]], [0,0], [0,3]))
Đầu vào
[[0,1],[1,0]], [0,0], [0,3]
Đầu ra
False