ZOJ 3652 Maze（BFS 搜尋迷宮）

題目大意

Celica 需在 n x m 迷宮中從 (x1, y1) 走到 (x2, y2)。每回合擁有行動力 l，每移動一步消耗 1，行動力歸零則進入下一回合（行動力恢復為 l）。迷宮中有怪物佔據特定格子，進入怪物佔據格子行動力立即歸零；若踩到怪物本體位置，可瞬間殺死怪物，其佔據區域變為普通格子。求最少回合數，無法到達輸出 We need God's help!。

關鍵規則

1. 每回合初始行動力 l，移動一格 -1，歸零換回合。
2. 踩到怪物位置立即殺死，其佔據區域解除。
3. 進入怪物佔據區域行動力立即歸零。
4. 每到達一格，先改變行動力再處理怪物邏輯（即踩到怪物且該格被佔據時，先歸零再殺怪）。
5. 怪物不一定在其佔據區域內；起點無怪物但可能被佔據。

解法分析：狀態壓縮 BFS

狀態包含：座標 (x, y)、當前回合數 ans、剩餘行動力 t、已殺怪物狀態 flag（最多 5 隻怪，用 5 位元表示）。使用優先隊列（小根堆）按回合數、剩餘行動力排序，保證最先到達終點即為最優解。三維 vis[x][y][flag] 防止重複狀態。

核心代碼

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
int n, m, l, k;
int sx, sy, ex, ey;
int mat[55][55], ms[55][55];
bool vis[55][55][32];
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

struct Node {
    int x, y, ans, t, flag;
    Node() {}
    Node(int x, int y, int ans, int t, int flag) : x(x), y(y), ans(ans), t(t), flag(flag) {}
    bool operator < (const Node &b) const {
        if (ans != b.ans) return ans > b.ans;
        return t < b.t;
    }
};

void bfs() {
    priority_queue<Node> q;
    vis[sx][sy][0] = true;
    q.push(Node(sx, sy, 0, l, 0));
    while (!q.empty()) {
        Node now = q.top(); q.pop();
        if (now.x == ex && now.y == ey) {
            if (now.t != l) now.ans++;
            cout << now.ans << endl;
            return;
        }
        for (int i = 0; i < 4; ++i) {
            int x = now.x + dir[i][0];
            int y = now.y + dir[i][1];
            if (x < 1 || x > n || y < 1 || y > m) continue;
            if (mat[x][y] == -1) continue;
            int t = now.t - 1;
            int flag = now.flag;
            if (mat[x][y] != 0) {
                int re = mat[x][y];
                if (!(flag & (1 << (re - 1)))) t = 0;
            }
            if (ms[x][y] >= 0) flag = flag | (1 << ms[x][y]);
            if (vis[x][y][flag]) continue;
            int ans = now.ans;
            if (t == 0) { t = l; ans++; }
            vis[x][y][flag] = true;
            q.push(Node(x, y, ans, t, flag));
        }
    }
    cout << "We need God's help!" << endl;
}

int main() {
    while (cin >> n >> m >> l) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                cin >> mat[i][j];
        cin >> k;
        memset(ms, -1, sizeof(ms));
        for (int i = 0; i < k; ++i) {
            int a, b; cin >> a >> b; ms[a][b] = i;
        }
        cin >> sx >> sy >> ex >> ey;
        if (sx == ex && sy == ey) { cout << 0 << endl; continue; }
        memset(vis, 0, sizeof(vis));
        bfs();
    }
    return 0;
}

樣例輸入/輸出

輸入：
5 5 4
2 2 2 1 0
-1 2 2 -1 1
2 2 2 1 1
1 1 1 0 1
2 2 -1 0 2
4
2 1
1 5
1 1
5 5
5 4
1 1 1 1 1 1
2 2 -1 -1 2 2
-1 2 2 -1 -1 2 2
2 2 2 2 2 2
2 2 2 2 2 2
1 2 1 1 5 5

輸出：
4
We need God's help!