# Sinh maze ngẫu nhiên: 0 = đường đi, 1 = tường, ép start/end là đường
import numpy as np
import matplotlib.pyplot as plt
from collections import deque
np.random.seed(7)

maze = np.random.choice([0, 1], size=(10, 10), p=[0.7, 0.3])
maze[0, 0] = 0
maze[9, 9] = 0

# BFS chuẩn: queue lưu (vị trí, path), visited tránh duyệt lại
def bfs(maze, start, end):
    rows, cols = maze.shape
    visited = {start}
    queue = deque([(start, [start])])
    while queue:
        (r, c), path = queue.popleft()
        if (r, c) == end:
            return path
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                and maze[nr, nc] == 0
                and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append(((nr, nc), path + [(nr, nc)]))
    return None

path = bfs(maze, (0, 0), (9, 9))
if path:
    print(f"Tìm thấy đường — {len(path)} bước")
else:
    print("Không có đường — sinh lại maze hoặc giảm tỷ lệ tường")

Tìm thấy đường — 19 bước

# Vẽ maze (đen=tường, trắng=đường), overlay đường đi BFS bằng line đỏ
fig, ax = plt.subplots(figsize=(8, 8))
ax.imshow(maze, cmap='binary', origin='upper')
if path:
    ys, xs = zip(*path)
    ax.plot(xs, ys, 'r-', linewidth=3, label=f'Đường ngắn nhất ({len(path)} bước)')
    ax.plot(0, 0, 'go', markersize=15, label='Bắt đầu')
    ax.plot(9, 9, 'b^', markersize=15, label='Kết thúc')
ax.set_xticks(range(10)); ax.set_yticks(range(10))
ax.grid(True, alpha=0.3); ax.legend(loc='upper right')
ax.set_title('BFS trên mê cung 10×10')
plt.show()

Thuật toán BFS — Tìm đường ngắn nhất trong mê cung 10×10¶

BFS implementation¶

Trực quan hóa¶

Kết luận¶