หลบพ้นเขาวงกตขนาดใหญ่ใน Python

สมมติว่ามีกริดขนาด 1 ล้านแถวและ 1 ล้านคอลัมน์ พร้อมรายการเซลล์ที่ถูกบล็อก เริ่มจากตำแหน่ง source ต้องการไปถึง target โดยเดินได้ทีละ 1 เซลล์ (บน ล่าง ซ้าย ขวา) ไม่ผ่านเซลล์ที่ถูกบล็อก ต้องตรวจสอบว่าสามารถไปถึงเป้าหมายได้หรือไม่

ตัวอย่าง: blocked = [[0,1],[1,0]], source = [0,0], target = [0,3] → ผลลัพธ์ False

ขั้นตอนการแก้ปัญหา

• สร้างเซตของเซลล์ที่ถูกบล็อก
• กำหนดฟังก์ชัน dfs(x, y, target, seen)
• ถ้า (x,y)อยู่นอกกริด หรืออยู่ใน blocked หรืออยู่ใน seen แล้ว → คืนค่า False
• เพิ่ม (x,y) ลงใน seen
• ถ้าขนาด seen > 20000 หรือ (x,y) คือ target → คืนค่า True
• เรียก dfs แบบrekursive 4 ทิศทาง
• คืนค่า dfs(source) และ dfs(target) ทั้งคู่

ตัวอย่างโค้ด

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]))

อินพุต

[[0,1],[1,0]], [0,0], [0,3]

เอาต์พุต

False