Chương trình Python tìm số bước tối thiểu thoát ma trận mê cung

Cho ma trận nhị phân: 0 = ô trống, 1 = tường. Từ góc trên trái (0,0) đến góc dưới phải (R-1, C-1), di chuyển 4 hướng. Tìm số ô tối thiểu đi qua (độ dài đường đi). Không có đường → trả về -1.

Ví dụ

matrix = [
  [0,0,0,1,0],
  [0,0,1,1,0],
  [0,0,0,1,1],
  [1,1,0,0,0]
]
Output: 8
Đường: (0,0)→(1,0)→(2,0)→(2,1)→(2,2)→(3,2)→(3,3)→(3,4)

Thuật toán: BFS (Breadth-First Search)

BFS đảm bảo tìm đường ngắn nhất trên đồ thị không trọng số.

1. Queue lưu (row, col, distance), khởi tạo (0,0,1) nếu ô bắt đầu = 0.
2. Đánh dấu ô đã thăm bằng gán matrix[r][c] = 1 (tận dụng ma trận input).
3. Pop queue, nếu đến đích → trả về distance.
4. Thêm 4 hàng xóm hợp lệ (trong bounds, giá trị 0) vào queue với distance+1.
5. Hết queue không thấy đích → trả về -1.

Code 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  # 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 matrix[x][y] == 0:
                matrix[x][y] = 1
                q.append((x, y, d + 1))
    
    return -1

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

Giải thích BFS queue iteration

Python for ... in q trên list đang append: iterator tự động lấy phần tử mới append → hành vi như queue (FIFO).

Độ phức tạp

• Thời gian: O(R × C) - mỗi ô thăm tối đa 1 lần.
• Không gian: O(R × C) cho queue (worst case).

Biến thể

• Trả về đường đi: lưu parent pointer.
• Diagonal moves: thêm 4 hướng chéo.
• Weighted grid: dùng Dijkstra (priority queue).