HDU 1026 Ignatius and the Princess I 解題：BFS 最短路徑與 DFS 路徑重建

題目大意

在 N×M 迷宮中，從 (0,0) 走到 (N-1,M-1)。格子類型：. 可走，X 陷阱不可走，1-9 殺怪需花費對應秒數。移動上下左右每步 1 秒。求最小總秒數並輸出完整路徑 (含戰鬥過程)。

演算法設計

1. BFS 求最短時間：狀態為座標 (x,y)。距離陣列 dist[x][y] 記錄到達該點的最小秒數。轉移：dist[nx][ny] = dist[x][y] + 1 + cost[nx][ny] (cost 為怪物血量，空地為 0)。使用隊列，類似 SPFA 鬆弛。
2. 記錄前驅：pre[x][y] 記錄上一步座標，用於路徑重建。
3. DFS 重建路徑並輸出：從終點遞歸回溯到起點，收集路徑節點。輸出時：移動步驟輸出 Ns:(x1,y1)->(x2,y2)；怪物格子輸出 Ns:FIGHT AT (x,y) 重複 cost 次。

關鍵程式碼結構

struct Node { int x, y; };
struct State { int dist; Node pre; int cost; }; // cost: 0=路, -1=陷阱, 1-9=怪物

State map[101][101];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

void bfs() {
    queue q;
    q.push({0,0});
    map[0][0].dist = map[0][0].cost; // 起點無怪物
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        for (auto &d : dir) {
            Node nxt = {cur.x+d[0], cur.y+d[1]};
            if (out of bounds or map[nxt].cost == -1) continue;
            int ndist = map[cur].dist + 1 + max(0, map[nxt].cost);
            if (map[nxt].dist == 0 || ndist < map[nxt].dist) {
                map[nxt].dist = ndist;
                map[nxt].pre = cur;
                q.push(nxt);
            }
        }
    }
}

void dfsPrint(State &s, Node cur) {
    if (cur.x == 0 && cur.y == 0) {
        // 輸出起點戰鬥 (若有)
        return;
    }
    dfsPrint(map[s.pre.x][s.pre.y], s.pre);
    // 輸出移動步驟
    // 輸出當前格子戰鬥 (若 cost>0)
}

注意事項

• 起點 (0,0) 保證無怪物，但邏輯上需處理 cost。
• 秒數計算：移動 1 秒 + 殺怪 n 秒 = n+1 秒從上一格進入此格。輸出格式嚴格對照 Sample。
• 多測資直到 EOF。