HDU 1026 Ignatius and the Princess I：BFS + 優先隊列解最短路徑

題目大意

n×m 地圖，'.' 空地，'X' 障礙，數字 '1'~'9' 表示怪獸（需停留該數秒）。從 (0,0) 走到 (n-1,m-1)，四向移動每步 1 秒，打怪額外耗時。求最短時間並輸出完整路徑（含打怪步驟）。

核心算法：Dijkstra / 0-1 BFS 變體

邊權非負（1+怪獸時間），用優先隊列 (最小堆) 實現 Dijkstra。狀態：(x, y, time)。訪問標記 vis[x][y] 確保每個格子只進隊一次（因 Dijkstra 保證首次出隊即最短）。

路徑記錄技巧

用 preDir[x][y] 記錄從哪個方向進入 (0:上,1:右,2:下,3:左)。輸出時從終點遞歸回溯到起點，再正序打印。打怪步驟單獨展開：若 map[x][y] > 0，輸出 k FIGHT AT (x,y) 行。

C++ 代碼

#include 
using namespace std;
struct Node {
    int x, y, t;
    bool operator<(const Node& o) const { return t > o.t; } // 小頂堆
};
const int MAXN = 105;
int mp[MAXN][MAXN], preDir[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

bool inGrid(int x, int y, int n, int m) {
    return x>=0 && x=0 && y pq;
    pq.push({0,0,0});
    vis[0][0] = true;
    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        if (cur.x == n-1 && cur.y == m-1) return cur.t;
        for (int d = 0; d < 4; ++d) {
            int nx = cur.x + dx[d], ny = cur.y + dy[d];
            if (!inGrid(nx,ny,n,m) || vis[nx][ny] || mp[nx][ny] == -1) continue;
            vis[nx][ny] = true;
            preDir[nx][ny] = d;
            pq.push({nx, ny, cur.t + 1 + mp[nx][ny]});
        }
    }
    return -1;
}

void printPath(int x, int y, int& step) {
    if (preDir[x][y] == -1) return;
    int d = preDir[x][y];
    int px = x - dx[d], py = y - dy[d];
    printPath(px, py, step);
    cout << step++ << "s:(" << px << "," << py << ")->(" << x << "," << y << ")\n";
    while (mp[x][y]-- > 0) cout << step++ << "s:FIGHT AT (" << x << "," << y << ")\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        string row;
        for (int i = 0; i < n; ++i) {
            cin >> row;
            for (int j = 0; j < m; ++j) {
                if (row[j] == '.') mp[i][j] = 0;
                else if (row[j] == 'X') mp[i][j] = -1;
                else mp[i][j] = row[j] - '0';
            }
        }
        int ans = dijkstra(n, m);
        if (ans == -1) {
            cout << "God please help our poor hero.\n";
        } else {
            cout << "It takes " << ans << " seconds to reach the target position, let me show you the way.\n";
            int step = 1;
            printPath(n-1, m-1, step);
        }
        cout << "FINISH\n";
    }
    return 0;
}

關鍵點

• 優先隊列比普通 BFS 正確處理帶權邊（打怪時間）。
• vis 在入隊時標記，保證每點只進隊一次，時間複雜度 O(nm log(nm))。
• 路徑回溯用遞歸，簡潔易懂；step 參考傳遞保證全局步數遞增。

總結

HDU 1026 是「網格最短路徑 + 路徑輸出」的經典入門題。核心模板：Dijkstra + 優先隊列 + 方向前驅數組 + 遞歸回溯輸出。同模板解決 POJ 3278、Codeforces 迷宮最短路徑等問題。