HDU 1026 Ignatius and the Princess I 迷宮最短路徑 BFS + 路徑記錄

題目背景

N×M 迷宮，從 (0,0) 走到 (N-1,M-1)。地圖字符含義：

• . 空地，耗時 1 秒
• X 陷阱，不可通行
• 1-9 怪物，進入需額外花費 n 秒擊殺

求最小總耗時並輸出完整路徑（含戰鬥步驟）。

演算法選擇：Dijkstra（優先隊列 BFS）

因邊權非均勻（1 或 1+n），普通 BFS 不適用，需 Dijkstra 算法。狀態：(x, y, time)，優先隊列按 time 升序。

路徑重構技巧

1. dir[x][y] 記錄到達 (x,y) 時的移動方向（0:下, 1:上, 2:右, 3:左）
2. 終點回溯至起點，構建路徑棧
3. 正序輸出，遇怪物格子展開戰鬥步驟

關鍵代碼片段

struct Node {
    int x, y, t;
    bool operator<(const Node& o) const { return t > o.t; } // 小頂堆
};

int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
int dir[105][105], dist[105][105];
char grid[105][105];

bool dijkstra(int n, int m) {
    memset(dist, 0x3f, sizeof(dist));
    dist[0][0] = 0;
    priority_queue<Node> pq;
    pq.push({0,0,0});

    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        if (cur.t != dist[cur.x][cur.y]) continue;
        if (cur.x == n-1 && cur.y == m-1) return true;

        for (int d = 0; d < 4; ++d) {
            int nx = cur.x + dx[d], ny = cur.y + dy[d];
            if (nx<0||nx>=n||ny<0||ny>=m) continue;
            if (grid[nx][ny] == 'X') continue;

            int nt = cur.t + 1;
            if (isdigit(grid[nx][ny])) nt += grid[nx][ny] - '0';

            if (nt < dist[nx][ny]) {
                dist[nx][ny] = nt;
                dir[nx][ny] = d;
                pq.push({nx,ny,nt});
            }
        }
    }
    return false;
}

void printPath(int n, int m) {
    vector<pair<int,int>> path;
    int x = n-1, y = m-1;
    while (x!=0 || y!=0) {
        path.emplace_back(x,y);
        int d = dir[x][y];
        x -= dx[d]; y -= dy[d];
    }
    path.emplace_back(0,0);
    reverse(path.begin(), path.end());

    int sec = 0;
    for (size_t i = 1; i < path.size(); ++i) {
        auto [px,py] = path[i-1];
        auto [cx,cy] = path[i];
        printf("%ds:(%d,%d)->(%d,%d)\n", ++sec, px,py, cx,cy);
        if (isdigit(grid[cx][cy])) {
            int hp = grid[cx][cy]-'0';
            while (hp--) printf("%ds:FIGHT AT (%d,%d)\n", ++sec, cx,cy);
        }
    }
    printf("FINISH\n");
}

注意事項

• 起點不含怪物，終點可能含怪物（需戰鬥）
• 多測試案例，EOF 結束
• 輸出格式嚴格對應樣例，含 FINISH 行