POJ 1915 Knight Moves：雙向 BFS 求騎士最短路徑完整解析與 C++ 實作

題目大意

給定 l × l 棋盤 (4 ≤ l ≤ 300) 及起點、終點座標，求國際象棋「騎士」從起點移動到終點的最少步數。騎士移動方式為 8 向「日」字走法。

雙向 BFS 核心思想

• 同時從**起點**與**終點**展開 BFS，兩個佇列輪流擴展一層。
• 若某節點被**兩端**同時訪問，或**一端擴展的下一層**碰到另一端已訪問節點，即找到最短路徑。
• 搜尋空間從 O(b^d) 降為 O(b^(d/2))，b=8、d 為答案步數，極大加速。

關鍵資料結構

const int MAXL = 330;
int vis1[MAXL][MAXL]; // 起點端距離，-1 表未訪問
int vis2[MAXL][MAXL]; // 終點端距離
int dx[8] = {2,2,-2,-2,1,1,-1,-1};
int dy[8] = {1,-1,1,-1,2,-2,2,-2};
struct Node { int x, y; };

雙向 BFS 完整流程

void biBFS(int sx, int sy, int ex, int ey, int l) {
    memset(vis1, -1, sizeof(vis1));
    memset(vis2, -1, sizeof(vis2));
    queue<Node> q, w;
    q.push({sx, sy}); vis1[sx][sy] = 0;
    w.push({ex, ey}); vis2[ex][ey] = 0;
    
    while (!q.empty() && !w.empty()) {
        // 擴展起點端一層
        int qs = q.size();
        while (qs--) {
            Node cur = q.front(); q.pop();
            if (vis2[cur.x][cur.y] != -1) { // 相遇
                cout << vis1[cur.x][cur.y] + vis2[cur.x][cur.y] << '\n';
                return;
            }
            for (int i=0;i<8;i++) {
                int nx = cur.x + dx[i], ny = cur.y + dy[i];
                if (nx<0||nx>=l||ny<0||ny>=l) continue;
                if (vis2[nx][ny] != -1) { // 下一層碰到終點端
                    cout << vis1[cur.x][cur.y] + 1 + vis2[nx][ny] << '\n';
                    return;
                }
                if (vis1[nx][ny] == -1) {
                    vis1[nx][ny] = vis1[cur.x][cur.y] + 1;
                    q.push({nx, ny});
                }
            }
        }
        // 擴展終點端一層 (對稱邏輯)
        int ws = w.size();
        while (ws--) {
            Node cur = w.front(); w.pop();
            if (vis1[cur.x][cur.y] != -1) {
                cout << vis1[cur.x][cur.y] + vis2[cur.x][cur.y] << '\n';
                return;
            }
            for (int i=0;i<8;i++) {
                int nx = cur.x + dx[i], ny = cur.y + dy[i];
                if (nx<0||nx>=l||ny<0||ny>=l) continue;
                if (vis1[nx][ny] != -1) {
                    cout << vis2[cur.x][cur.y] + 1 + vis1[nx][ny] << '\n';
                    return;
                }
                if (vis2[nx][ny] == -1) {
                    vis2[nx][ny] = vis2[cur.x][cur.y] + 1;
                    w.push({nx, ny});
                }
            }
        }
    }
}

複雜度分析

• 時間：O(l^2) 最壞全盤遍歷，但雙向 BFS 實際訪問節點數約為單向 BFS 平方根。
• 空間：兩個 l×l 整數陣列 + 兩佇列，l≤300 時約 2×300×300×4B ≈ 720KB，極小。

測試樣例

Input:
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

Output:
5
28
0

常見錯誤與優化

1. 忘記判斷 起點=終點 直接輸出 0。
2. 單向 BFS 配合 vis 陣列也可 AC，但 l=300 時最壞訪問 90,000 節點，仍在時限內；雙向 BFS 更穩健。
3. 佇列擴展順序：必須**逐層**擴展 (用 size() 控制)，否則無法保證最短路徑層數正確。
4. 相遇條件包含「當前節點已被另一端訪問」與「下一層節點已被另一端訪問」兩種，漏掉後者會導致奇數步答案錯誤。