題目大意

N×M 迷宮（≤8×8），牆壁（X）、起點（S）、終點（D）、空地（.）、炸彈（1-9）。初始無炸彈，撿到炸彈可炸牆（消耗 1 炸彈 + 1 秒）。移動上下左右 1 格/秒。求最少時間到達終點，不可達輸出 -1。

核心建模：狀態壓縮 + 優先隊列（Dijkstra）

• 地圖除起終點外 ≤62 格，可用 64 位整數壓縮狀態：
  • 哪些炸彈已撿起
  • 哪些牆壁已炸毀
• 狀態：(x, y, time, bomb_count, state_mask)
• 優先隊列按 time 排序（小頂堆），保證最短時間優先展開
• 訪問標記：vis[x][y][bomb_count] 存儲已到達的 state_mask 集合，新狀態若被已有狀態支配（mask1 | mask2 == mask1 且炸彈數 ≥）則剪枝

關鍵轉移

1. 移動到空地/炸彈/終點：time+1，撿炸彈更新 bomb_count 和 mask
2. 移動到牆壁：若有炸彈，time+2（炸牆 1 秒 + 移動 1 秒），bomb_count-1，更新牆壁狀態位

代碼框架（C++）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#define LL unsigned long long
using namespace std;

int n, m;
char Map[10][10];
int Mp[10][10]; // 非牆/非起終點格的編號 0~61
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

struct Node {
    int x, y, t, boom;
    LL v; // 狀態掩碼
    friend bool operator<(Node a, Node b) { return a.t > b.t; }
    bool check() { return x>=0 && x<n && y>=0 && y<m; }
} st, ed;

vector<LL> vis[8][8][9*8*8+1]; // vis[x][y][boom] 存儲已到達的 mask

bool check_state(Node a) {
    for (LL m : vis[a.x][a.y][a.boom])
        if ((a.v | m) == m) return false; // 被支配
    return true;
}

void bfs() {
    priority_queue<Node> q;
    q.push(st);
    vis[st.x][st.y][st.boom].push_back(st.v);
    while (!q.empty()) {
        st = q.top(); q.pop();
        if (Map[st.x][st.y] == 'D') { printf("%d\n", st.t); return; }
        for (int i=0; i<4; i++) {
            ed = st; ed.t++; ed.x += dir[i][0]; ed.y += dir[i][1];
            if (!ed.check()) continue;
            char c = Map[ed.x][ed.y];
            if (c == 'X') { // 牆壁
                if (ed.boom > 0) {
                    ed.boom--; ed.t++; // 炸牆額外 1 秒
                    ed.v |= (1LL << Mp[ed.x][ed.y]); // 標記牆已炸
                    if (check_state(ed)) {
                        vis[ed.x][ed.y][ed.boom].push_back(ed.v);
                        q.push(ed);
                    }
                }
            } else if (c >= '1' && c <= '9') { // 炸彈
                int id = Mp[ed.x][ed.y];
                if ((ed.v & (1LL << id)) == 0) { // 未撿過
                    ed.boom += c - '0';
                    ed.v |= (1LL << id);
                }
                if (check_state(ed)) {
                    vis[ed.x][ed.y][ed.boom].push_back(ed.v);
                    q.push(ed);
                }
            } else { // 空地、終點、起點
                if (check_state(ed)) {
                    vis[ed.x][ed.y][ed.boom].push_back(ed.v);
                    q.push(ed);
                }
            }
        }
    }
    printf("-1\n");
}

int main() {
    while (cin >> n >> m) {
        if (n==0 && m==0) break;
        memset(Mp, -1, sizeof(Mp));
        int len = 0;
        for (int i=0; i<n; i++) {
            cin >> Map[i];
            for (int j=0; j<m; j++) {
                if (Map[i][j]=='X' || (Map[i][j]>='0' && Map[i][j]<='9'))
                    Mp[i][j] = len++;
                else if (Map[i][j]=='S') {
                    st.x=i; st.y=j; st.t=0; st.boom=0; st.v=0;
                }
            }
        }
        // 初始化 vis
        for (int i=0; i<8; i++)
            for (int j=0; j<8; j++)
                for (int k=0; k<9*8*8+1; k++)
                    vis[i][j][k].clear();
        bfs();
    }
    return 0;
}

優化要點

• 狀態支配剪枝：同位置、同炸彈數下，mask1 包含 mask2（資源更多）則 mask2 可捨棄
• 64 位掩碼完美覆蓋 62 格狀態
• 優先隊列保證首次到達終點即為最短時間