回溯算法解決迷宮問題（Java 實現）

回溯算法解決迷宮問題（Java 實現）

給定 M×N 矩陣迷宮，0 表示通路，1 表示牆壁。從左上角 (0,0) 走到右下角 (M-1,N-1)，只能上下左右移動，求所有可行路徑。本文提供標準回溯模板，並以 9×8 迷宮為例輸出 8 條路徑。

算法流程

1. 定義 int[][] maze 存儲迷宮，5 標記已走路徑；
2. 從 (0,0) 開始，依嘗試 右、左、下、上 四個方向；
3. canMove 校驗：越界、牆壁、已訪問均不可行；
4. 遞歸進入下一格，回溯時恢復標記（maze[i][j] = 0）；
5. 到達終點打印路徑矩陣。

完整代碼

public class MazeSolver {
    private final int[][] maze = {
        {0,0,1,0,0,0,1,0},
        {0,0,1,0,0,0,1,0},
        {0,0,1,0,1,1,0,1},
        {0,1,1,1,0,0,1,0},
        {0,0,0,1,0,0,0,0},
        {0,1,0,0,0,1,0,1},
        {0,1,1,1,1,0,0,1},
        {1,1,0,0,0,1,0,1},
        {1,1,0,0,0,0,0,0}
    };
    private final int ROWS = 9, COLS = 8;

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        new MazeSolver().dfs(0, 0);
        System.out.println("耗時: " + (System.currentTimeMillis() - start) + "ms");
    }

    private void dfs(int r, int c) {
        if (r == ROWS - 1 && c == COLS - 1) {
            printPath();
            return;
        }
        // 四個方向：右、左、下、上
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (canMove(nr, nc)) {
                maze[r][c] = 5; // 標記
                dfs(nr, nc);
                maze[r][c] = 0; // 回溯恢復
            }
        }
    }

    private boolean canMove(int r, int c) {
        if (r < 0 || c < 0 || r >= ROWS || c >= COLS) return false;
        if (maze[r][c] == 1 || maze[r][c] == 5) return false;
        return true;
    }

    private void printPath() {
        System.out.println("得到一個解：");
        for (int[] row : maze) {
            for (int v : row) System.out.print(v + " ");
            System.out.println();
        }
    }
}

運行結果與分析

• 程序在 3ms 內找到所有 8 條路徑；
• 輸出矩陣中 5 代表路徑，直觀展示走法；
• 方向嘗試順序影響路徑輸出順序，但不影響完整性。