Mini-challenge — Maze solver: BFS shortest path + path reconstruction

Bạn đang làm tính năng tìm đường cho một game mobile: bản đồ là lưới ô vuông 100×100, một số ô là tường không đi qua được, nhân vật phải tìm đường ngắn nhất từ điểm xuất phát đến đích. Yêu cầu thêm: phải có đường đi cụ thể để làm animation cho nhân vật di chuyển, chỉ biết độ dài là chưa đủ.

Tức là ngoài "khoảng cách ngắn nhất", bạn còn cần dựng lại đường đi (path reconstruction): danh sách các ô từ start đến end theo thứ tự.

Bài này luyện BFS (bài 02) trên grid, kết hợp parent map để dựng lại đường đi. Dạng bài này gặp ở tìm đường trong game, điều hướng robot và LeetCode 1091.

Yêu cầu bài toán

Viết hàm shortestPath(maze) với API sau:

• Trả về: danh sách các ô (row, col) từ S đến E theo thứ tự đi. Trả về danh sách rỗng nếu không có đường đi.
• Chỉ 4 hướng: lên, xuống, trái, phải. Không đi chéo.
• Ký tự: # là tường (không đi qua), . là ô đi được, S là điểm xuất phát, E là đích.
• Ràng buộc: maze tối đa 1000×1000.

Starter pseudocode

shortestPath(maze):
    -- TODO: BFS từ S, theo dõi parent, reconstruct path
    return []

Trước khi gõ dòng code nào, hãy làm tay maze1 trên giấy: vẽ lưới, ghi hàng đợi và từng ô được thăm theo thứ tự, y như thói quen ở bài Làm tay trước khi làm máy. Rồi dành 20–25 phút tự làm trước khi xem gợi ý.

Test scenario

maze1:
  S . . #
  # # . #
  . . . .
  . # # E

-- Expected: path gồm 7 ô, tức 6 bước (S tọa độ (0,0) đến E tọa độ (3,3))
-- Một path hợp lệ: (0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(2,3)->(3,3)

maze2:
  S #
  # E

-- Expected: danh sách rỗng (không có đường -- S bị chặn bởi tường)

Gợi ý

Lời giải

shortestPath(maze):
    rows <- maze.length
    cols <- maze[0].length

    start <- findChar(maze, 'S')
    end   <- findChar(maze, 'E')
    if start = NIL hoặc end = NIL: return []

    -- parent[r][c] = cell đã dẫn đến (r,c); -1 nghĩa là chưa thăm
    parent[0..rows-1][0..cols-1] <- -1

    Q <- Queue rỗng
    Q.enqueue(start)
    -- Đánh dấu start đã thăm bằng sentinel tự trỏ (self-loop)
    parent[start.r][start.c] <- encode(start.r, start.c)

    DIRS <- [(-1,0),(1,0),(0,-1),(0,1)]

    while Q không rỗng:
        (r, c) <- Q.dequeue()
        if r = end.r và c = end.c:
            return reconstructPath(parent, start, end, cols)
        for each (dr, dc) trong DIRS:
            nr <- r + dr
            nc <- c + dc
            if isValid(maze, nr, nc) và parent[nr][nc] = -1:
                parent[nr][nc] <- encode(r, c)    -- đánh dấu đã thăm + lưu parent
                Q.enqueue((nr, nc))

    return []    -- E không thể tới

isValid(maze, r, c):
    return 0 <= r < rows và 0 <= c < cols và maze[r][c] != '#'

encode(r, c, cols):
    return r * cols + c

decode(e, cols):
    return (e / cols, e % cols)

reconstructPath(parent, start, end, cols):
    path <- []
    cur <- end
    while true:
        path.append(cur)
        prev <- decode(parent[cur.r][cur.c], cols)
        if prev = cur: break    -- đã về start (sentinel self-loop)
        cur <- prev
    path.reverse()
    return path

Bẫy phổ biến

Trước khi xem ba bẫy dưới, hãy tự liệt kê ca biên cho solver của bạn, theo cách ở bài Edge case: maze không có S hoặc không có E, E bị tường bao kín (như maze2), S đứng ngay cạnh E, maze chỉ có một hàng. Lời giải ở trên đã xử lý hai ca đầu bằng return [].

Bẫy 1: Mark visited khi DEQUEUE thay vì khi ENQUEUE.

Đây là cái bẫy cốt lõi đã gặp ở bài BFS: nếu đánh dấu đã thăm sau khi dequeue thay vì trước khi enqueue, cùng một ô có thể bị enqueue nhiều lần bởi nhiều ô kề khác nhau. Với grid dày đặc, queue phình ra rất nhanh và BFS chậm hẳn đi.

-- WRONG: mark khi dequeue -- cell (2,2) có thể bị enqueue nhiều lần
(r, c) <- Q.dequeue()
visited[r][c] <- true    -- quá muộn

-- CORRECT: mark khi enqueue -- parent[nr][nc] != -1 là "đã visited"
if parent[nr][nc] = -1:
    parent[nr][nc] <- encode(r, c)
    Q.enqueue((nr, nc))

Luôn đánh dấu trước khi enqueue, không đợi đến sau khi dequeue.

Bẫy 2: Kiểm tra biên sai.

-- BUG: dùng <= thay <
if nr <= rows và nc <= cols:    -- off-by-one: index rows out of bound

-- CORRECT
if 0 <= nr < rows và 0 <= nc < cols:

rows là số hàng nên index hợp lệ chạy từ 0 đến rows - 1. Hãy luôn viết nr < rows, đừng viết nr <= rows - 1 (tương đương nhưng dễ nhầm khi sửa code).

Bẫy 3: Mã hoá ô bị trùng khi maze lớn.

-- RISKY nếu maze có hơn 10000 cột:
encode(r, c) = r * 10000 + c
-- Nếu c >= 10000, encode(r, c1) và encode(r+1, c2) có thể va chạm

-- SAFE: dùng số cột thực tế
encode(r, c, cols) = r * cols + c
-- Luôn unique vì c < cols nên không có collision

Với ràng buộc maze tối đa 1000×1000 của bài này, cả hai cách đều an toàn. Nhưng r * cols + c mới là cách đúng trong trường hợp tổng quát.

Benchmark tham khảo

BFS trên lưới 1000×1000 (1 triệu ô) phải duyệt tối đa gần cả triệu ô, và đó vẫn là khối lượng nhỏ cho một máy hiện đại; thời gian cụ thể tuỳ ngôn ngữ, máy và cách cài. Bidirectional BFS và A* thường duyệt ít ô hơn khi S và E gần nhau hoặc khi cần nhiều query liên tiếp, nhưng khó cài đặt đúng hơn nhiều. BFS là mốc đối chiếu đúng và đơn giản nhất.

Variant để tự thử

Đi 8 hướng (có đường chéo): thêm 4 hướng (-1,-1),(-1,1),(1,-1),(1,1). BFS vẫn chỉ đếm số cạnh, nhưng bước chéo thực tế dài căn bậc hai của 2. Nếu muốn "khoảng cách Euclid nhỏ nhất" thì BFS không còn đúng, cần Dijkstra với weight 1.0 cho bước thẳng và 1.414 cho bước chéo.

Multi-source BFS, nhiều điểm xuất phát: enqueue tất cả S vào queue ngay từ đầu (distance 0 cho tất cả). BFS lan ra cùng lúc từ mọi nguồn, tìm đường ngắn nhất từ tập nguồn đến E trong O(V + E) bất kể có bao nhiêu nguồn. Dạng này giống LeetCode 994 Rotting Oranges.

Maze có trọng số (chi phí địa hình): mỗi ô 0-9 có cost tương ứng. BFS không còn đúng, cần Dijkstra với MinHeap theo tổng cost. Xem bài 05 trong module này.

A* với heuristic Manhattan: thay Queue bằng MinHeap theo g(n) + h(n) với h = |r - endR| + |c - endC|. Dừng sớm khi dequeue ra E. Trên maze lớn, A* nhanh hơn BFS nhiều vì không phải duyệt hết mọi hướng.

Sinh maze: dùng DFS quay lui ngẫu nhiên (backtracking) để tạo maze trước khi giải. Đây là bước tiếp theo tự nhiên để thử solver với nhiều maze khác nhau.

Thử ngẫmkhi cho đi chéo, khoảng cách Euclid thật của bước chéo là căn 2, nhưng BFS vẫn tính mỗi cạnh là 1. Nếu maze của bạn cho bước chéo "rẻ" ngang bước thẳng thì BFS dùng tạm được; còn nếu muốn tính đúng khoảng cách thật, thuật toán nào trong module này thay được BFS?

LeetCode liên quan

• 1091. Shortest Path in Binary Matrix — BFS 8 hướng trên binary grid, gần với bài này nhất.
• 994. Rotting Oranges — multi-source BFS, nhiều nguồn cùng lan ra một lúc.
• 542. 01 Matrix — multi-source BFS, tìm khoảng cách đến ô 0 gần nhất.
• 127. Word Ladder — BFS với cạnh nối hai từ khác nhau đúng 1 ký tự. Vẫn là bài đường ngắn nhất, nhưng graph là graph các từ thay vì grid.

Ghi chú ứng dụng

Tìm đường trong game (NPC di chuyển): BFS là bản cơ sở để học thuật toán. Game thật dùng A* trên grid: heuristic Manhattan giúp dừng sớm, NPC tìm đường nhanh hơn nhiều so với BFS quét toàn bộ. Nhiều engine (Unity NavMesh chẳng hạn) chạy A* trên navigation mesh, tức đồ thị các đa giác đi được, thay vì lưới ô thô.

Điều hướng robot (ROS): robot dùng occupancy grid (mỗi ô cho biết có vật cản hay không). Package move_base của ROS có global planner chạy Dijkstra hoặc A* trên costmap dạng lưới ô này, nên bài mini-challenge hôm nay là phiên bản thu nhỏ của đúng bài toán đó.

Tìm đường GPS: thay vì grid, graph là mạng đường với cạnh có trọng số. Dijkstra thuần khá nặng khi mạng có hàng triệu node, nên nhiều engine routing tiền xử lý bằng contraction hierarchies (CH): tính trước các cạnh tắt để bỏ qua node trung gian, nhờ đó truy vấn nhanh hơn rất nhiều (xem bài case study).

Điều bạn vừa làm được

• Cài đặt BFS trên grid 2D: mỗi ô là một vertex, bước sang ô kề theo 4 hướng là một cạnh.
• Kết hợp parent[] để dựng lại đường ngắn nhất, từ đó có cả đường đi cụ thể chứ không chỉ khoảng cách.
• Hiểu vì sao phải mark visited khi enqueue (không phải khi dequeue) để giữ O(V + E).
• Mã hoá (row, col) thành số nguyên để lưu parent gọn, và biết cách tránh trùng mã khi maze lớn.
• Nhận ra BFS trên grid là nền tảng của tìm đường trong game, điều hướng robot, GPS và hàng loạt bài LeetCode.

Bài tiếp theo: Case Study: Maven DAG + Google Maps routing