HDU 4771 Stealing Harry Potter's Precious：BFS+全排列收集寶物

HDU 4771 Stealing Harry Potter's Precious：BFS+全排列收集寶物

N×M 網格，`#` 不可通行，`.` 可通行，`@` 起點。K≤4 個寶物位置給定。從起點出發收集所有寶物，不需返回，求最少步數。不可重複訪問格子？題目未明確，但 BFS 自然不重複訪問。

核心思路：寶物少 → 全排列枚舉收集順序

K ≤ 4，全排列數 ≤ 24。對每種順序，依次 BFS 從當前位置到下一寶物，累加距離。取最小總距離。

算法流程

1. 讀入網格，記錄起點 `@` 和 K 個寶物位置
2. 生成寶物索引數組 `p[0..K-1]` 的全排列
3. 對每個排列：
   • 從起點 BFS 到 `p[0]`
   • 從 `p[0]` BFS 到 `p[1]`
   • ...
   • 若某段不可達，該排列無效
   • 累加距離，更新最小值
4. 輸出最小值，無有效排列輸出 -1

BFS 實現細節

int bfs(int sx, int sy, int tx, int ty) {
    queue<Node> q;
    q.push({sx, sy, 0});
    vis[sx][sy] = true;
    while (!q.empty()) {
        auto [x, y, d] = q.front(); q.pop();
        if (x == tx && y == ty) return d;
        for 4方向:
            if 合法且未訪問且非'#':
                vis[nx][ny] = true;
                q.push({nx, ny, d+1});
    }
    return -1; // 不可達
}

優化：單次 BFS 多目標

原代碼在單次 BFS 中按順序尋找下一目標，到達後清空隊列重置 visited 繼續找下一個。這比每段單獨 BFS 更快（避免重複掃描公共前綴路徑）。

int bfs_sequence(const vector<Point> &targets) {
    queue<Node> q;
    q.push({start_x, start_y, 0});
    memset(vis, 0, sizeof(vis));
    vis[start_x][start_y] = 1;
    
    int target_idx = 0;
    while (!q.empty() && target_idx < targets.size()) {
        auto [x, y, d] = q.front(); q.pop();
        for 4方向:
            nx, ny, nd = d+1
            if 合法:
                if (nx == targets[target_idx].x && ny == targets[target_idx].y) {
                    // 到達當前目標
                    target_idx++;
                    if (target_idx == targets.size()) return nd;
                    // 重置 BFS 狀態從當前位置繼續找下一目標
                    while (!q.empty()) q.pop();
                    memset(vis, 0, sizeof(vis));
                    q.push({nx, ny, nd});
                    vis[nx][ny] = 1;
                    break; // 跳出方向循環
                }
                vis[nx][ny] = 1;
                q.push({nx, ny, nd});
    }
    return -1;
}

完整代碼框架

int main() {
    while (cin >> n >> m && n) {
        // 讀網格，找起點
        cin >> K;
        vector<Point> gems(K);
        for (i=0..K-1) cin >> gems[i].x >> gems[i].y, --x, --y;
        
        vector<int> perm(K);
        iota(perm.begin(), perm.end(), 0);
        
        int ans = -1;
        do {
            vector<Point> seq;
            for (idx : perm) seq.push_back(gems[idx]);
            int dist = bfs_sequence(seq);
            if (dist != -1 && (ans == -1 || dist < ans)) ans = dist;
        } while (next_permutation(perm.begin(), perm.end()));
        
        cout << ans << "\n";
    }
}

關鍵細節

複雜度

• 全排列：K! ≤ 24
• 單次 BFS：O(NM) ≤ 10⁴
• 總計：O(K! × NM) ≤ 2.4×10⁵，極快

此題展示了「少量關鍵點 + 全排列枚舉順序 + 多目標 BFS」的經典解題模式，將 TSP 類問題在小 K 時完美解決。