จำนวนการเคลื่อนที่น้อยที่สุดเพื่อหนีเขาวงกตเมทริกซ์ใน Python

คำอธิบายปัญหา

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

ตัวอย่าง

Matrix:
0 0 0 1 0
0 0 1 1 0
0 0 0 1 1
1 1 0 0 0

Output: 8 (เส้นทาง: (0,0)→(1,0)→(2,0)→(2,1)→(2,2)→(3,2)→(3,3)→(3,4) = 8 เซลล์)

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

1. คิว q เริ่มต้น [(0,0,1)] หาก (0,0) เป็น 0
2. ทำเครื่องหมาย matrix[0][0] = 1 (visited)
3. BFS: pop (r,c,d) ถ้าถึงปลายทาง คืน d
4. ตรวจสอบ 4 ทิศทาง: ในขอบเขต และเป็น 0 → mark=1, push (nr,nc,d+1)
5. จบลูปไม่เจอ → คืน -1

การตนการทำงาน (Python)

def solve(matrix):
    R, C = len(matrix), len(matrix[0])
    q = [(0, 0, 1)] if not matrix[0][0] else []
    matrix[0][0] = 1
    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 matrix[x][y] == 0:
                matrix[x][y] = 1
                q.append((x, y, d + 1))
    return -1

matrix = [
    [0, 0, 0, 1, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 1, 1],
    [1, 1, 0, 0, 0]
]
print(solve(matrix))  # Output: 8

อินพุต / เอาต์พุต

Input:  [[0,0,0,1,0],[0,0,1,1,0],[0,0,0,1,1],[1,1,0,0,0]]
Output: 8