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

Bạn đang build tính năng pathfinding cho một game mobile: bản đồ là lưới ô vuông 100×100, một số ô là tường không thể đi qua, 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: hiển thị đường đi thực tế để animate nhân vật di chuyển — không chỉ độ dài.

Tức là bạn cần không chỉ "shortest distance" mà còn cả "path reconstruction" — danh sách ô từ start đến end theo thứ tự.

Bài này luyện BFS (lesson 02) trên grid + parent map cho path reconstruction. Pattern này dùng cho game pathfinding, robot navigation, 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.
• 4-direction only: up, down, left, right. Không có diagonal.
• Ký tự: # là tường (không đi qua), . là đường, S là start, E là end.
• Constraint: maze tối đa 1000×1000.

Starter pseudocode

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

Dành 20–25 phút tự làm trước khi xem gợi ý.

Test scenario

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

-- Expected: path length 7 (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

graph TD
    subgraph "Sóng BFS lan từ S trên maze1"
        S00["S(0,0)\ntầng 0"] --> C01["(0,1)\ntầng 1"]
        C01 --> C02["(0,2)\ntầng 2"]
        C02 --> C12["(1,2)\ntầng 3"]
        C12 --> C22["(2,2)\ntầng 4"]
        C22 --> C23["(2,3)\ntầng 5"]
        C22 --> C21["(2,1)\ntầng 5"]
        C23 --> E33["E(3,3)\ntầng 6"]
    end

Pitfall phổ biến

Pitfall 1 — Mark visited khi DEQUEUE thay khi ENQUEUE.

Giống pitfall cốt lõi trong lesson 02 BFS — nếu mark visited sau khi dequeue thay vì trước khi enqueue, cùng một cell có thể được enqueue nhiều lần bởi nhiều neighbor khác nhau. Với grid dày đặc, queue phình ra phi tuyến, BFS trở nên rất chậm.

-- 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 mark trước khi enqueue, không phải sau khi dequeue.

Pitfall 2 — Bound check sai chiều.

-- 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 — index hợp lệ là 0 đến rows - 1. Luôn dùng nr < rows, không phải nr <= rows - 1 (tương đương nhưng dễ nhầm khi chỉnh sửa).

Pitfall 3 — Encode tile index bị collision với 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 constraint maze tối đa 1000×1000 trong bài này, cả hai cách đều an toàn. Nhưng dùng r * cols + c là pattern đúng về mặt tổng quát.

Benchmark tham khảo

Maze 1000x1000 (1 triệu cell), khoảng 70% ô đi được, start/end ngẫu nhiên:
  BFS đơn giản:          khoảng 50ms  (worst case: duyệt gần 1M cell)
  Bidirectional BFS:     khoảng 30ms  (hai đầu gặp nhau giữa)
  A* với Manhattan:      khoảng 10ms  (early termination, khi S và E gần nhau)

BFS là baseline đúng đắn và đơn giản nhất. Bidirectional BFS và A* tối ưu hơn khi maze lớn hoặc cần nhiều query liên tiếp — nhưng phức tạp hơn đáng kể để implement đúng.

Variant để tự thử

8-direction (diagonal): thêm 4 direction (-1,-1),(-1,1),(1,-1),(1,1). BFS vẫn đếm số cạnh nhưng diagonal thực tế có khoảng cách căn bậc hai của 2 — nếu muốn "khoảng cách Euclidean nhỏ nhất" thì BFS không còn chính xác. Cần Dijkstra với weight 1.0 cho thẳng và 1.414 cho diagonal.

Multi-source BFS — nhiều điểm start: enqueue tất cả S vào queue ban đầu (distance 0 cho tất cả). BFS lan ra đồng thời từ mọi nguồn — tìm đường ngắn nhất từ tập nguồn đến E trong O(V + E) không quan tâm số nguồn. Pattern này giống LeetCode 994 Rotting Oranges.

Weighted maze (terrain cost): mỗi cell 0-9 có cost tương ứng. BFS không còn đúng — cần Dijkstra với MinHeap theo tổng cost. Bài học 05 trong module này.

A* với Manhattan heuristic: thay Queue bằng MinHeap theo g(n) + h(n) với h = |r - endR| + |c - endC|. Early termination khi dequeue ra E — thực tế nhanh hơn BFS nhiều trên large maze vì không cần duyệt hết mọi hướng.

Maze generation: backtracking DFS ngẫu nhiên để tạo maze trước khi solve — bước tự nhiên tiếp theo để test solver với nhiều maze khác nhau.

LeetCode liên quan

• 1091. Shortest Path in Binary Matrix — 8-direction BFS trên binary grid, closest match với bài này.
• 994. Rotting Oranges — multi-source BFS, nhiều nguồn lan ra đồng thời.
• 542. 01 Matrix — multi-source BFS, tìm khoảng cách đến cell 0 gần nhất.
• 127. Word Ladder — BFS với edge = "2 word khác nhau đúng 1 ký tự", cùng pattern shortest path nhưng graph là word graph thay vì grid.

Applied note

Game pathfinding (NPC movement): BFS là baseline dạy thuật toán. Production game dùng A* trên grid — heuristic Manhattan giúp early termination, NPC tìm đường nhanh hơn nhiều so với BFS scan toàn bộ. Unity NavMesh dùng variant của A* + navigation mesh thay vì raw grid.

Robot navigation (ROS): robot dùng occupancy grid — mỗi cell có probability là tường hay không. BFS/Dijkstra cho map đã biết (known map), A* cho map có thể dự đoán, D* Lite cho map thay đổi động (robot khám phá dần). Package move_base trong ROS là concrete implementation.

GPS routing: thay vì grid, graph là road network với weighted edge (travel time hoặc distance). Dijkstra thuần túy quá chậm với triệu node — production dùng contraction hierarchies (CH): precompute "shortcut edge" để skip node trung gian, query gần như instant.

CAPTCHA solver preprocessing: BFS connected components trên image segmentation — xác định vùng ký tự liên thông, tách ký tự ra trước khi nhận dạng.

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

• Implement BFS trên 2D grid: model cell là vertex, 4-direction neighbor là edge.
• Kết hợp parent[] map để reconstruct shortest path — không chỉ distance mà còn cả đường đi cụ thể.
• Hiểu tại sao mark visited khi enqueue (không phải dequeue) là bắt buộc để giữ O(V + E).
• Encode (row, col) thành số nguyên để lưu parent gọn — và biết cách tránh collision khi maze lớn.
• Nhận ra pattern BFS-on-grid là nền tảng của game pathfinding, robot navigation, GPS routing, và hàng loạt LeetCode problem.

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