POJ 3984 迷宮問題：BFS 求最短路徑並輸出路徑 (父節點回溯法)

問題描述

固定 5×5 迷宮，0 為路，1 為牆。從 (0,0) 走到 (4,4)，只能上下左右移動，數據保證唯一解。輸出最短路徑座標序列，格式 (r, c) 空格分隔。

BFS + 父節點記錄

由於邊權均為 1，BFS 自然得到最短路。關鍵在於如何輸出路徑：

• 維護 father[x][y] 記錄前驅節點 (編碼為單一整數 x*5+y)。
• 到達終點後，從終點按 father 回溯到起點，存入棧/數組再正序輸出。

完整代碼

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 5;
int maze[N][N];
int dist[N][N];
int father[N*N]; // 扁平化存父節點編碼
int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};

struct Pos { int x, y; };

void printPath(int endCode) {
    int path[30], top = 0;
    for (int cur = endCode; cur != 0; cur = father[cur])
        path[top++] = cur;
    path[top++] = 0; // 起點 (0,0) 編碼為 0
    for (int i = top-1; i >= 0; --i) {
        cout << '(' << path[i]/5 << ", " << path[i]%5 << ')';
        if (i) cout << ' ';
    }
    cout << '\n';
}

int main() {
    for (int i=0;i> maze[i][j];

    memset(dist, 0x3f, sizeof(dist));
    queue q;
    q.push({0,0});
    dist[0][0] = 0;
    father[0] = -1;

    while (!q.empty()) {
        Pos p = q.front(); q.pop();
        if (p.x == 4 && p.y == 4) {
            printPath(p.x*5 + p.y);
            break;
        }
        for (int d=0; d<4; ++d) {
            int nx = p.x + dx[d], ny = p.y + dy[d];
            if (nx<0||nx>=N||ny<0||ny>=N) continue;
            if (maze[nx][ny] == 1) continue;
            if (dist[nx][ny] != 0x3f3f3f3f) continue;
            dist[nx][ny] = dist[p.x][p.y] + 1;
            father[nx*5+ny] = p.x*5 + p.y;
            q.push({nx,ny});
        }
    }
    return 0;
}

關鍵點總結

• 扁平化編碼 x*5+y 簡化父節點存儲 (一維數組足夠)。
• 起點編碼 0，father[0] = -1 作為回溯終止條件。
• 輸出格式嚴格：(0, 0) 逗號後有空格，座標間單空格，行末換行。
• 題目保證唯一解，無需處理多條最短路情況。