Thoát khỏi mê cung lớn trong Python

Giả sử chúng ta có một lưới có 1 triệu hàng và 1 triệu cột, cùng với một danh sách các ô bị chặn. Chúng ta bắt đầu từ ô nguồn và muốn đến ô đích. Ở mỗi bước, chúng ta có thể đi đến ô liền kề lên, xuống, trái, phải trong lưới mà không nằm trong danh sách ô bị chặn.

Chúng ta phải kiểm tra xem có thể đến ô đích thông qua một chuỗi các bước di chuyển hay không.

Ví dụ: nếu đầu vào là blocked = [[0,1],[1,0]], source = [0,0], target = [0,3], thì kết quả sẽ là False.

Để giải quyết bài toán này, chúng ta thực hiện các bước sau:

• blocked := tạo một tập hợp (set) chứa tất cả các ô bị chặn
• Định nghĩa phương thức dfs(), nhận tham số x, y, target và seen
• Nếu (x,y) không trong phạm vi lưới HOẶC (x,y) nằm trong blocked HOẶC (x,y) đã nằm trong seen thì trả về false
• Thêm (x,y) vào seen
• Nếu kích thước seen > 20000 HOẶC (x,y) là target thì trả về true
• Trả về 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)
• Trả về dfs(source[0], source[1], target, empty set) AND dfs(target[0], target[1], source, empty set)

Hãy xem 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