Khóa học Python từ Cơ bản đến Nâng cao

Bài 12.7 - Python: giải bài đi trong mê cung

Bài toán tìm đường đi trong mê cung là một bài toán kinh điển để áp dụng thuật toán tìm kiếm đường đi, thường dùng BFS hoặc DFS để tìm từ điểm xuất phát đến đích.

Mô tả mê cung

• Mê cung được biểu diễn bằng ma trận 2 chiều.
• '0' là đường đi được.
• '1' là tường.
• Bạn được phép đi lên, xuống, trái, phải.

Ví dụ mê cung

maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0]
]
start = (0, 0)
end = (4, 4)

Tìm đường đi ngắn nhất từ (0,0) đến (4,4)

Giải bằng thuật toán BFS

BFS rất phù hợp để tìm đường đi ngắn nhất trong mê cung không trọng số.

Cài đặt bằng Python

from collections import deque

def shortest_path(maze, start, end):
    rows, cols = len(maze), len(maze[0])
    visited = [[False]*cols for _ in range(rows)]
    queue = deque([(start, [start])])

    directions = [(-1,0), (1,0), (0,-1), (0,1)]

    while queue:
        (r, c), path = queue.popleft()
        if (r, c) == end:
            return path

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and maze[nr][nc] == 0:
                visited[nr][nc] = True
                queue.append(((nr, nc), path + [(nr, nc)]))

    return None  # Không tìm thấy đường

Chạy ví dụ

path = shortest_path(maze, start, end)
print("Đường đi ngắn nhất:", path)

Kết quả:

Đường đi ngắn nhất: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]

Chương trình trả về danh sách các ô từ điểm bắt đầu đến điểm đích.

Giải thích code

• queue lưu từng bước đi và đường đi đã đi qua.
• Mỗi bước duyệt ra 4 hướng: trên, dưới, trái, phải.
• Nếu đích được tìm thấy, trả về đường đi ngắn nhất.
• Dùng mảng visited để tránh lặp lại ô đã đi qua.

Tùy chọn nâng cao

• Chỉ kiểm tra có đường đi hay không: Không cần lưu path, chỉ cần True/False.
• Đếm số bước thay vì đường:

  return len(path) - 1
  

• In mê cung với đường đi được đánh dấu (ví dụ với dấu *).

Độ phức tạp

Trong đó:

• m là số hàng
• n là số cột

Gợi ý mở rộng

• Tìm tất cả các đường đi từ A đến B
• Mê cung có nhiều điểm xuất phát hoặc nhiều điểm kết thúc
• Mê cung có trọng số → dùng Dijkstra

Tổng kết

• Bài toán đi trong mê cung là ví dụ tuyệt vời cho thuật toán tìm đường.
• BFS rất phù hợp để tìm đường đi ngắn nhất trong mê cung không trọng số.
• Bạn có thể tùy biến bài toán để luyện thêm các kỹ năng giải thuật: DFS, đánh dấu, đệ quy,...