題目場景

n×m 迷宮（≤50×50），起點 (x1,y1) 終點 (x2,y2)。每回合行動力 l (≤10)，移動一格消耗 1，耗盡進入下一回合（行動力恢復 l）。地圖格子：-1 不可進入，0 正常，>0 表示被第 p 個怪物統治。進入怪物統治格行動力歸零（強制換回合）。怪物站在某格（不一定在自己統治區），進入該格可秒殺怪物，其統治區變為正常格。怪物 ≤5 個，不移動。求最少回合數，不可達輸出 We need God's help!。

核心建模：狀態壓縮 BFS

• 狀態：(x, y, killed_mask, remaining_power)
  • killed_mask：5 位掩碼，標記已殺怪物（≤5 個 → 32 種）
  • remaining_power：當前回合剩餘行動力（0~l）
• 四維訪問數組：vis[55][55][1<<5][11]
• 優先隊列（或雙端隊列）按回合數 T 排序，保證最少回合優先展開

關鍵轉移規則

1. 移動到相鄰格 (nx,ny)：
   • 若為 -1：不可進入
   • 若被活著的怪物統治：new_power = 0，new_T = T+1
   • 若為怪物位置：殺死怪物（更新 killed_mask），該格及其統治區變正常，new_power--
   • 否則：new_power--
2. new_power == 0 時強制換回合：new_T++，new_power = l
3. 到達終點即可返回當前回合數 T（即使 power=0 也不需等下一回合）

坑點提醒

• 起點 = 終點：答案為 1 回合（題目保證起點無怪物）
• 怪物可能不在自己統治區，甚至在無統治區
• 進入格子時，行動力變化優先於其他判定（PS3）

代碼框架（C++）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#define inf 1<<30
#define LL long long
using namespace std;

int Map[55][55], Mp[55][55]; // 地圖、怪物位置
bool vis[55][55][1<<6][11];
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int n, m, l, k;

struct Node {
    int x, y, t, T, vis_mask; // 坐標、剩餘行動力、回合數、殺怪掩碼
    bool check() { return x>0 && x<=n && y>0 && y<=m; }
    friend bool operator<(Node a, Node b) { return a.T > b.T; } // 小頂堆
} st, ed;

void bfs() {
    priority_queue<Node> q;
    st.t = l; st.T = 1; st.vis_mask = 0;
    q.push(st);
    vis[st.x][st.y][st.vis_mask][st.t] = true;

    while (!q.empty()) {
        Node cur = q.top(); q.pop();
        if (cur.x == ed.x && cur.y == ed.y) {
            cout << cur.T << endl; return;
        }
        // 行動力為 0 強制換回合
        if (cur.t == 0) {
            Node nxt = cur; nxt.t = l; nxt.T++;
            if (!vis[nxt.x][nxt.y][nxt.vis_mask][nxt.t]) {
                vis[nxt.x][nxt.y][nxt.vis_mask][nxt.t] = true;
                q.push(nxt);
            }
            continue;
        }
        // 嘗試 4 方向移動
        for (int i=0; i<4; i++) {
            Node nxt = cur;
            nxt.x += dir[i][0]; nxt.y += dir[i][1]; nxt.t--;
            if (!nxt.check() || Map[nxt.x][nxt.y] == -1) continue;
            // 處理怪物統治、殺怪邏輯...
            // 更新 nxt.vis_mask, nxt.t, nxt.T
            if (!vis[nxt.x][nxt.y][nxt.vis_mask][nxt.t]) {
                vis[nxt.x][nxt.y][nxt.vis_mask][nxt.t] = true;
                q.push(nxt);
            }
        }
    }
    cout << "We need God's help!" << endl;
}

int main() {
    while (cin >> n >> m >> l) {
        // 讀地圖、怪物位置、起終點
        // 初始化、調用 bfs()
    }
    return 0;
}