HDU 1429 迷宮問題：BFS + 狀態壓縮（鑰匙位圖）

問題描述

n,m ≤ 20 迷宮，包含：起點 @、終點 ^、牆 *、門 A-J（需對應鑰匙）、鑰匙 a-j。鑰匙拾取後永久擁有，可開對應門。求最短步數到達終點，且步數 ≤ 給定時間限制，否則輸出 -1。多測試用例。

狀態壓縮 BFS

• 狀態：(x, y, keys, steps)，keys 為 10 位位圖（1<<10 = 1024），第 i 位表示擁有鑰匙 'a'+i。
• 訪問標記：vis[x][y][keys] 三維數組。
• 轉移：四方向移動。目標格為門且無鑰匙 → 跳過。目標格為鑰匙 → 更新 keys。其餘正常。
• BFS 保證最短步數。到達終點 ^ 即返回步數。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
const int MAXK = 1<<10;
struct State { int x, y, keys, step; };

int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
char grid[MAXN][MAXN];
bool vis[MAXN][MAXN][MAXK];
int n, m, time_limit;

int bfs(int sx, int sy) {
    memset(vis, 0, sizeof(vis));
    queue q;
    q.push({sx, sy, 0, 0});
    vis[sx][sy][0] = true;
    while (!q.empty()) {
        State cur = q.front(); q.pop();
        if (grid[cur.x][cur.y] == '^') return cur.step;
        for (int d = 0; d < 4; ++d) {
            int nx = cur.x + dx[d], ny = cur.y + dy[d];
            if (nx<0||nx>=n||ny<0||ny>=m) continue;
            char c = grid[nx][ny];
            if (c == '*') continue;
            State nxt = cur;
            nxt.x = nx; nxt.y = ny; nxt.step++;
            if (c >= 'A' && c <= 'J') {
                int need = c - 'A';
                if (!(cur.keys & (1<= 'a' && c <= 'j') {
                nxt.keys = cur.keys | (1 << (c - 'a'));
            }
            if (!vis[nxt.x][nxt.y][nxt.keys]) {
                vis[nxt.x][nxt.y][nxt.keys] = true;
                q.push(nxt);
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n >> m >> time_limit) {
        int sx, sy;
        for (int i = 0; i < n; ++i) {
            cin >> grid[i];
            for (int j = 0; j < m; ++j)
                if (grid[i][j] == '@') sx = i, sy = j;
        }
        int ans = bfs(sx, sy);
        if (ans != -1 && ans < time_limit) cout << ans << '\n';
        else cout << -1 << '\n';
    }
    return 0;
}

複雜度

狀態數 ≤ 20×20×1024 ≈ 4×10^5，BFS 邊數 ≤ 4×狀態數，時間空間均可接受。

關鍵點

1. 鑰匙位圖完美契合「拾取後永久生效」且種類少（≤10）。
2. 門檢查：keys & (1<。
3. 鑰匙拾取：keys | (1<。
4. 時間限制判斷在 BFS 返回後進行。