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 class MazeSolver với API sau:

• List<int[]> shortestPath(char[][] maze) — trả về list các ô (row, col) từ 'S' đến 'E' theo thứ tự đi. Trả về list 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 code

import java.util.*;

public class MazeSolver {
    public List<int[]> shortestPath(char[][] maze) {
        // TODO: BFS from S, track parent, reconstruct path
        return List.of();
    }
}

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

Test scenario

char[][] maze1 = {
    {'S', '.', '.', '#'},
    {'#', '#', '.', '#'},
    {'.', '.', '.', '.'},
    {'.', '#', '#', 'E'}
};
// Expected: path length 7 (S toa do (0,0) den E toa do (3,3))
// One valid path: (0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(2,3)->(3,3)

char[][] maze2 = {
    {'S', '#'},
    {'#', 'E'}
};
// Expected: empty list (no path -- S bi chan boi tuong)

Gợi ý

Lời giải

import java.util.*;

public class MazeSolver {
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public List<int[]> shortestPath(char[][] maze) {
        int rows = maze.length;
        int cols = maze[0].length;

        int[] start = findChar(maze, 'S');
        int[] end   = findChar(maze, 'E');
        if (start == null || end == null) return List.of();

        // parent[r][c] = encoded previous cell; -1 means not visited yet.
        int[][] parent = new int[rows][cols];
        for (int[] row : parent) Arrays.fill(row, -1);

        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(start);
        // Mark start visited by setting parent to itself (self-loop sentinel).
        parent[start[0]][start[1]] = encode(start[0], start[1]);

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            if (cell[0] == end[0] && cell[1] == end[1]) {
                return reconstructPath(parent, start, end);
            }
            for (int[] d : DIRECTIONS) {
                int nr = cell[0] + d[0];
                int nc = cell[1] + d[1];
                if (isValid(maze, nr, nc) && parent[nr][nc] == -1) {
                    parent[nr][nc] = encode(cell[0], cell[1]); // mark visited + store parent
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        return List.of(); // E unreachable
    }

    private boolean isValid(char[][] maze, int r, int c) {
        return r >= 0 && r < maze.length
            && c >= 0 && c < maze[0].length
            && maze[r][c] != '#';
    }

    private int[] findChar(char[][] maze, char target) {
        for (int r = 0; r < maze.length; r++) {
            for (int c = 0; c < maze[0].length; c++) {
                if (maze[r][c] == target) return new int[]{r, c};
            }
        }
        return null;
    }

    private int encode(int r, int c) { return r * 10000 + c; }
    private int[] decode(int e) { return new int[]{e / 10000, e % 10000}; }

    private List<int[]> reconstructPath(int[][] parent, int[] start, int[] end) {
        List<int[]> path = new ArrayList<>();
        int[] cur = end;
        while (true) {
            path.add(cur);
            int[] prev = decode(parent[cur[0]][cur[1]]);
            // Stop when we reach start (self-loop sentinel: prev == cur)
            if (prev[0] == cur[0] && prev[1] == cur[1]) break;
            cur = prev;
        }
        Collections.reverse(path);
        return path;
    }
}

Pitfall phổ biến

Pitfall 1 — Mark visited khi POP thay khi PUSH.

Giống pitfall cốt lõi trong lesson 02 BFS — nếu mark visited sau khi poll thay vì trước khi push vào queue, 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 poll -- cell (2,2) co the bi push nhieu lan
int[] cell = queue.poll();
visited[cell[0]][cell[1]] = true; // too late

// CORRECT: mark khi push -- parent[nr][nc] != -1 la "da visited"
if (parent[nr][nc] == -1) {
    parent[nr][nc] = encode(cell[0], cell[1]);
    queue.offer(new int[]{nr, nc});
}

Luôn mark trước khi push, không phải sau khi pop.

Pitfall 2 — Bound check sai chiều.

// BUG: dung <= thay <
if (nr <= maze.length && nc <= maze[0].length) // off-by-one: index maze.length out of bound

// CORRECT
if (nr >= 0 && nr < maze.length && nc >= 0 && nc < maze[0].length)

maze.length là số hàng — index hợp lệ là 0 đến maze.length - 1. Luôn dùng < maze.length, không phải <= maze.length - 1 (tương đương nhưng dễ nhầm khi chỉnh sửa).

Pitfall 3 — Encode tile index bị overflow với maze lớn.

// RISKY nếu maze > 10000 cột:
private int encode(int r, int c) { return r * 10000 + c; }
// Nếu c >= 10000, encode (r, c1) va (r+1, c2) co the trung nhau.

Với constraint maze tối đa 1000×1000 trong bài này, c < 10000 luôn đúng — r * 10000 + c an toàn. Nhưng khi maze lớn hơn (vd 100000×100000), cần dùng r * cols + c với cols thực tế, hoặc dùng int[] trực tiếp trong parent map (Map thay mảng 2D) để tránh tính toán encode hoàn toàn.

Benchmark tham khảo

Maze 1000x1000 (1 trieu cell), ~70% o di duoc, start/end ngau nhien:
  BFS don gian:          ~50ms  (worst case: duyet gan 1M cell)
  Bidirectional BFS:     ~30ms  (hai dau gap nhau giua)
  A* voi Manhattan:      ~10ms  (early termination, khi S va E gan 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 √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: push 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 PriorityQueue min-heap theo tổng cost. Bài học 05 trong module này.

A* với Manhattan heuristic: thay Queue bằng PriorityQueue theo g(n) + h(n) với h = |r - endR| + |c - endC|. Early termination khi pop 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 push (không phải pop) là bắt buộc để giữ O(V + E).
• Encode (row, col) thành int để lưu parent gọn — và biết giới hạn overflow 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