萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

POJ 1915 Knight Moves:雙向 BFS 求騎士最短路徑完整解析

問題描述:給定 l × l 棋盤(4 ≤ l ≤ 300),騎士從起點 (sx, sy) 移動到終點 (ex, ey),求最小步數。騎士移動方式為「日」字形(8 個方向)。多測試用例。

算法選擇:雙向 BFS

  • 單向 BFS 狀態空間最大 300×300=90,000,雙向 BFS 將搜索深度減半,時間/空間複雜度約降為 O(b^(d/2)),極大提升速度。
  • 兩端同時擴展,當某節點被兩端同時訪問時,路徑長度 = 兩端步數之和。

關鍵數據結構

int vis1[330][330]; // 起點端訪問標記+步數,-1 表示未訪問
int vis2[330][330]; // 終點端訪問標記+步數
int fx[8] = {2,2,-2,-2,1,1,-1,-1};
int fy[8] = {1,-1,1,-1,2,-2,2,-2};

struct Node { int x, y; };
queue<Node> q, w; // 兩端隊列

核心邏輯

void biBFS() {
    memset(vis1, -1, sizeof(vis1));
    memset(vis2, -1, sizeof(vis2));
    
    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) {
                printf("%d\n", vis1[cur.x][cur.y] + vis2[cur.x][cur.y]);
                return;
            }
            // 擴展 8 方向
            for (int i = 0; i < 8; ++i) {
                Node nxt = {cur.x + fx[i], cur.y + fy[i]};
                if (inside(nxt.x, nxt.y) && vis1[nxt.x][nxt.y] == -1) {
                    vis1[nxt.x][nxt.y] = vis1[cur.x][cur.y] + 1;
                    // 關鍵優化:檢查下一層是否已被終點端訪問(奇數步相遇)
                    if (vis2[nxt.x][nxt.y] != -1) {
                        printf("%d\n", vis1[nxt.x][nxt.y] + vis2[nxt.x][nxt.y]);
                        return;
                    }
                    q.push(nxt);
                }
            }
        }
        // 再擴展終點端一層(對稱邏輯)
        int ws = w.size();
        while (ws--) { /* 同理,檢查 vis1 */ }
    }
}

關鍵細節解析

  1. 雙端交替擴展:每次各擴展一層,保證兩端深度差 ≤ 1,最先相遇即為最短路徑。
  2. 奇數步相遇處理:擴展時檢查下一層節點是否已被對端訪問,捕捉「當前層→下一層」的相遇情況(步數和 +1)。
  3. 邊界檢查:0 ≤ x,y < l。
  4. 起點=終點:初始化時 vis1[sx][sy]=0, vis2[ex][ey]=0,若同點則首次檢查即返回 0。

複雜度分析

  • 時間:O(l²) 最壞情況全盤遍歷,但雙向實測極快(< 10ms)。
  • 空間:兩個 330×330 int 陣列 ≈ 0.8 MB,兩隊列同數量級。

測試樣例

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

Output:
5
28
0

避坑提示

  • 數組大小開 ≥ 305 防越界。
  • memset 初始化 -1 必須用 sizeof 而非固定大小。
  • 輸入可能包含多組測試用例,主循環讀 n 後逐個處理。
  • C++ 用 scanf/printf 或關閉同步 ios::sync_with_stdio(false) 加速 IO。

雙向 BFS 是解決大狀態空間最短路徑的經典技巧,掌握其「交替擴展 + 相遇檢查」模板,可輕鬆應對 POJ 1915 等同類問題。

copyright © 萬盛學電腦網 all rights reserved