HDU 3567 Eight II - 八數碼變體：任意起止狀態雙向 BFS 預處理

題目大意

同八數碼，但給定任意起始狀態 A 和目標狀態 B，求最短操作序列（字典序最小）。T ≤ 200，保證可解。需輸出步數與操作串。

核心觀察：預處理所有狀態到目標的最短路徑

八數碼總狀態數 9! = 362,880，但空格位置不同導致 9 個連通分量（空格位置固定時為 8! = 40,320 狀態）。預處理：以目標狀態 12345678x 為起點，對每個空格位置 (0~8) 分別運行 BFS，記錄所有狀態到該目標的最短距離與操作。查詢時將 A 映射到對應空格位置的預處理結果，直接輸出路徑。

映射技巧：重新標號

查詢給定 A、B。先將 B 視為「新目標」，計算其康拓值 targetHash。然後將 A 中的數字按 B 中的位置重新標號：B 中位置 i 的數字 → 新標號 i。這樣轉換後的 A 到「標準目標 12345678x」的路徑，即為原 A 到 B 的路徑。

預處理代碼框架 (C++)

// 9 個空格位置分別 BFS
vector> pre(9), act(9); // pre[空格位置][hash] = 前驅hash, act = 操作
void bfs(int blankPos) {
    // 起始狀態：空格在 blankPos，其餘 1..8 順序
    // 標準 BFS，記錄 pre, act
}

int main() {
    // 預處理 9 次 BFS
    for (int i = 0; i < 9; ++i) bfs(i);

    int T; cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        string A, B; cin >> A >> B;
        // 計算 B 的康拓值 targetHash
        // 將 A 按 B 重新標號得到 A'
        // 空格位置 = A' 中 0 的索引
        // 在 pre[空格位置] 中回溯從 A' 到 targetHash 的路徑
        // 輸出步數與操作串 (按字典序 d,l,r,u 對應 0,1,2,3)
    }
}

關鍵點

1. 離線預處理：將多查詢轉化為單次 BFS + O(1) 查詢，總時間 O(9·8! + T·路徑長) 極快。
2. 重新標號映射：巧妙將任意目標 B 統一為標準目標，復用預處理結果。
3. 字典序最小：BFS 展開方向順序固定為 d, l, r, u (對應字典序)，首次到達即為字典序最小路徑。

總結

Eight II 展示了「狀態空間較小、多查詢、固定目標」場景下離線預處理的威力。重新標號映射是將任意目標歸一化的關鍵技巧。面試中能說清預處理邏輯、映射原理、字典序保證，即可展示對圖搜索與狀態空間的深度理解。