โปรแกรมหาเส้นทางสั้นสุดใน Maze ไปมุมล่างขวา (Python BFS)

ปัญหา

กำหนด 2D grid maze: 0 = ทางเดิน, 1 = ผนัง
เริ่มที่ (0,0) หาจำนวนเซลล์น้อยที่สุดเพื่อไป (R-1, C-1) ถ้าไม่ถึง → -1

ตัวอย่าง: 3x3 grid → 5 steps

วิธีแก้: BFS (Breadth-First Search)

BFS ให้ shortest path ใน unweighted graph โดยอัตโนมัติ

อัลกอริทึม

1. Queue เก็บ (row, col, distance)
2. เริ่มที่ (0,0,1) ถ้าไม่ใช่ผนัง
3. Mark visited โดยตั้ง grid[r][c] = 1
4. Dequeue ถ้าถึง destination → return distance
5. Enqueue เพื่อนบ้าน 4 ทิศที่ valid และยังไม่ visited
6. Queue ว่าง → return -1

โค้ด Python

class Solution:
    def solve(self, A):
        R, C = len(A), len(A[0])
        q = [(0, 0, 1)] if not A[0][0] else []
        A[0][0] = 1  # mark visited
        
        for r, c, d in q:
            if (r, c) == (R - 1, C - 1):
                return d
            for x, y in [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]:
                if 0 <= x < R and 0 <= y < C and A[x][y] == 0:
                    A[x][y] = 1
                    q.append((x, y, d + 1))
        return -1

# ทดสอบ
ob = Solution()
grid = [
    [0, 0, 0],
    [1, 0, 0],
    [1, 0, 0]
]
print(ob.solve(grid))  # 5

# Path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2) = 5 cells

ความซับซ้อน

• Time: O(R × C) - เยี่ยมแต่ละเซลล์สูงสุด 1 ครั้ง
• Space: O(R × C) - queue + grid modification

ข้อสังเกต

• แก้ไข grid ตรงๆ เพื่อ mark visited (ประหยัด memory)
• ใช้ list เป็น queue (index-based iteration) แทน collections.deque
• Distance เริ่มที่ 1 (นับ starting cell)

Variation: คืนค่า Path จริง

def solve_with_path(self, A):
    R, C = len(A), len(A[0])
    parent = {}
    q = deque([(0, 0)])
    A[0][0] = 1
    parent[(0, 0)] = None
    
    while q:
        r, c = q.popleft()
        if (r, c) == (R-1, C-1):
            # Reconstruct path
            path = []
            while (r, c) is not None:
                path.append((r, c))
                r, c = parent[(r, c)]
            return path[::-1]
        for x, y in [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]:
            if 0<=x