Java 棧與回溯法解迷宮問題完整實作

前言

迷宮尋路是棧與回溯算法的經典應用。本文採用二維陣列表示迷宮，結合自訂 Stack 與 LinkedList 隊列，完整實現「探路（回溯）」與「路徑優化」兩階段算法，並附完整可執行代碼與輸出示例。

迷宮表示規範

輸入格式：每行一字串，以 Ctrl+D (EOF) 結束。程式自動在四周包一層牆（邊界保護）。

核心數據結構

座標類 MazeCell

public class MazeCell {
    private int x, y;
    public MazeCell(int x, int y) { this.x=x; this.y=y; }
    public boolean equals(Object o) { /* 比較 x,y */ }
    public String toString() { return x+","+y; }
    // getter/setter
}

泛型棧 Stack<T> (基於 LinkedList)

public class Stack<T> {
    private LinkedList<T> storage = new LinkedList<>();
    public void push(T v) { storage.addFirst(v); }
    public T pop() { return storage.removeFirst(); }
    public T peek() { return storage.getFirst(); }
    public boolean empty() { return storage.isEmpty(); }
}

算法流程

階段一：探路與回溯 (DFS + 回溯)

1. 從入口開始，檢查上下左右四方向。
2. 發現出口 → 成功結束。
3. 將所有可通行鄰居（值為 0 或 9）壓入棧。
4. 棧彈出一座標作為新當前點，標記為 3（已訪問）。
5. 重複 1-4，直到棧空（失敗）或到達出口。
6. 回溯本質：無路可走時，自動彈出棧頂回到上一個決策點嘗試其他方向。

階段二：路徑優化 (刪除繞路)

探路過程中所有經過點（含回溯路徑）按順序存入 List<MazeCell>（隊列）。優化算法：

1. 從隊尾（出口）向前掃描。
2. 若發現某前驅節點與當前節點相鄰（曼哈頓距離=1），刪除中間所有節點。
3. 將該前驅節點設為新當前節點，繼續向前掃描。
4. 直到到達隊頭（入口）。

結果保證無回頭/繞路，但不一定是絕對最短路徑（需 BFS 或 Dijkstra）。

完整核心代碼

public class Maze {
    private char[][] store, path;  // 原始迷宮、路徑輸出
    private MazeCell entryCell, exitCell, currentCell;
    private Stack<MazeCell> mazeStack = new Stack<>();
    private List<MazeCell> currentList = new LinkedList<>(); // 探路軌跡

    public Maze() { /* 從 stdin 讀取、建立邊界、定位入口出口 */ }

    // 探路主邏輯
    public void exitMaze(PrintStream out) {
        currentCell = entryCell;
        currentList.add(currentCell);
        while (!currentCell.equals(exitCell)) {
            display(out, store);
            int r = currentCell.getX(), c = currentCell.getY();
            if (!currentCell.equals(entryCell)) store[r][c] = '3';
            pushUnvisited(r-1,c); pushUnvisited(r+1,c);
            pushUnvisited(r,c-1); pushUnvisited(r,c+1);
            if (mazeStack.empty()) { out.println("Failure"); return; }
            currentCell = mazeStack.pop();
            currentList.add(currentCell);
        }
        out.println("Success");
    }

    private void pushUnvisited(int r, int c) {
        if (store[r][c]=='0' || store[r][c]=='9') mazeStack.push(new MazeCell(r,c));
    }

    // 路徑優化
    private void getPath() {
        MazeCell cell = currentList.get(currentList.size()-1); // 出口
        while (cell != currentList.get(0)) { // 直到入口
            List<MazeCell> sub = currentList.subList(0, currentList.indexOf(cell));
            for (MazeCell target : sub) {
                if (adjoin(cell, target)) {
                    removeElements(currentList.indexOf(target)+1, currentList.indexOf(cell));
                    cell = target; break;
                }
            }
        }
    }
    private boolean adjoin(MazeCell a, MazeCell b) {
        return (Math.abs(a.getX()-b.getX())==1 && a.getY()==b.getY()) ||
               (Math.abs(a.getY()-b.getY())==1 && a.getX()==b.getX());
    }
    // 輸出最終路徑
    public void printPath(PrintStream out) { /* 標記 path 陣列並列印 */ }
}

運行示例

輸入:
90000
11011
00000
00600

輸出過程 (節錄):
// 初始迷宮 (含邊界牆)
1111111
1900001
1110111
1000001
1006001
1111111

// 探路與回溯動畫...
// 最終成功
Success
Path:
1111111
1933001
1113111
1003001
1006001
1111111

總結

棧天然支援 DFS 回溯，隊列記錄完整軌跡便於事後優化。此實作展示了：邊界保護簡化邏輯、泛型棧/隊列復用、回溯與優化分離。若需最短路徑，可改用 BFS（隊列）或 A* 算法。