HDU 1429 勝利大逃亡(續)：BFS + 狀態壓縮處理鑰匙門問題

題目大意

n×m 迷宮（n,m≤20），@ 起點，^ 終點，* 牆，a-j 鑰匙，A-J 對應門。限時 t 步內到達終點。求最短步數，不可達輸出 -1。

狀態設計：位置 + 持有鑰匙集合

• 位置：(x,y)
• 鑰匙狀態：mask，10 位對應 a~j，1 表示持有
• 訪問標記：vis[x][y][mask]，三維數組去重

狀態數上限：20×20×2¹⁰ = 400×1024 ≈ 41萬，BFS 完全可行。

BFS 遷移邏輯

struct Node { int x, y, mask, step; };

int bfs() {
    queue<Node> q;
    q.push({sx, sy, 0, 0});
    vis[sx][sy][0] = true;
    
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (cur.step >= T) continue;
        if (cur.x == ex && cur.y == ey) 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 cell = mp[nx][ny];
            if (cell == '*') continue;           // 牆
            if (vis[nx][ny][cur.mask]) continue; // 已訪問
            
            int nmask = cur.mask;
            if (cell >= 'A' && cell <= 'J') {    // 門
                int need = cell - 'A';
                if (!(cur.mask & (1<= 'a' && cell <= 'j') {    // 撿鑰匙
                nmask |= 1 << (cell - 'a');
            }
            
            vis[nx][ny][nmask] = true;
            q.push({nx, ny, nmask, cur.step+1});
        }
    }
    return -1;
}

關鍵優化點

1. 三維訪問數組：vis[x][y][mask] 區分不同鑰匙狀態下到達同一位置，避免錯誤剪枝。
2. 鑰匙狀態單調增長：只增不減，同一位置最多訪問 2¹⁰ 次。
3. 步數限制剪枝：cur.step >= T 直接丟棄。
4. 早期終止：出隊即檢查是否到達終點，保證最短步數。

完整代碼（含輸入處理）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
const int MAXM = 1<<10;

int n, m, T;
char mp[MAXN][MAXN];
bool vis[MAXN][MAXN][MAXM];
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};
int sx, sy, ex, ey;

struct Node { int x, y, mask, step; };

int bfs() {
    memset(vis, 0, sizeof(vis));
    queue<Node> q;
    q.push({sx, sy, 0, 0});
    vis[sx][sy][0] = true;
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (cur.step >= T) continue;
        if (cur.x == ex && cur.y == ey) 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 = mp[nx][ny];
            if (c == '*') continue;
            if (vis[nx][ny][cur.mask]) continue;
            int nmask = cur.mask;
            if (c >= 'A' && c <= 'J') {
                int need = c - 'A';
                if (!(cur.mask & (1<= 'a' && c <= 'j') {
                nmask |= 1 << (c - 'a');
            }
            vis[nx][ny][nmask] = true;
            q.push({nx, ny, nmask, cur.step+1});
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n >> m >> T) {
        for (int i=0;i> mp[i];
            for (int j=0;j

複雜度分析

  
狀態數：O(n·m·2^k)，k=10 固定
  
每狀態轉移 O(4)
  
總時間 O(n·m·2^k) ≈ 400×1024×4 ≈ 1.6e6，極快
  
空間 vis[20][20][1024] ≈ 400KB


拓展：網絡賽同類題更難點

  
多把鑰匙開同一門、門可重複通過、鑰匙可丟棄
  
需更複雜的狀態機或 A* 啟發式搜索