โปรแกรมเช็คว่าบุคคลหนีไฟไปมุมซ้ายบนหรือขวาล่างได้หรือไม่ใน Python

คำอธิบายโจทย์

เมทริกซ์: 0=ว่าง, 1=คน, 2=ไฟ, 3=กำแพง ไฟขยาย 4 ทิศทางทีละเทิร์น (ไม่ทะลุกำแพง) คนเดินก่อน แล้วไฟขยาย ถ้าคนถึงมุมเป้าหมายพร้อมไฟก็รอด ตรวจสอบว่าหนีไป (0,0) หรือ (R-1,C-1) ได้ไหม

ตัวอย่าง

เมทริกซ์ 3x3 คนอยู่ (1,2) ไฟอยู่ (2,2) → True (หนีไป (0,0) ได้)

วิธีแก้ปัญหา

Multi-source BFS คำนวณระยะทาง:

1. BFS จากไฟทั้งหมด → dist_fire[cell] = เวลาที่ไฟถึง
2. BFS จากคน → dist_person[cell] = เวลาที่คนถึง
3. เช็คมุม (0,0) และ (R-1,C-1): ถ้า dist_person ≤ dist_fire → รอด (True)
4. ใช้ deque สำหรับ BFS

โค้ด Python

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

อินพุต

[[0, 0, 0], [0, 0, 1], [0, 0, 2]]

เอาต์พุต

True