HDU 5094 Maze：BFS + 狀態壓縮（鑰匙門）

題目

n×m 迷宮，有牆、門（需對應鑰匙）、鑰匙。從 (1,1) 到 (n,m) 最短步數。p ≤ 10 種鑰匙，狀態壓縮 2^p。

狀態定義

state = (x, y, keys)，keys 為 p 位掩碼，第 i 位=1 表示擁有鑰匙 i。

BFS 轉移

• 四方向嘗試移動。
• 目標格為牆（gate=0）跳過。
• 目標格為門（gate>0）需 keys & (1<<(gate-1))。
• 到達鑰匙格：newKeys = keys | keyMask[x][y]（可能有多把鑰匙）。
• 訪問數組 vis[x][y][keys] 防重複。

代碼片段

struct State { int x,y,keys,step; };
queue q;
q.push({1,1,0,0});
vis[1][1][0]=1;
while (!q.empty()) {
    auto cur = q.front(); q.pop();
    if (cur.x==n && cur.y==m) { ans=cur.step; break; }
    cur.keys |= keyMask[cur.x][cur.y];
    for (dir=0..3) {
        nx, ny;
        if (out of bounds) continue;
        int gate = gateMap[cur.x][cur.y][nx][ny];
        if (gate==0) continue; // 牆
        if (gate>0 && !(cur.keys & (1<<(gate-1)))) continue; // 無鑰匙
        if (!vis[nx][ny][cur.keys]) {
            vis[nx][ny][cur.keys]=1;
            q.push({nx,ny,cur.keys,cur.step+1});
        }
    }
}

複雜度

狀態數 ≤ n*m*2^p ≤ 50*50*1024 ≈ 2.5e6，BFS 可行。