HDU 1026 Ignatius and the Princess I（BFS+優先隊列）

卡了好久的題 伴随着我把實驗室的電腦從win8->win10->Ubuntu

題意：從(0,0)到(n-1,m-1)的最短時間并列印路徑

跟普通的BFS不一樣的地方是每個位置會有怪獸，是以不能就簡單的直接考慮路徑，打怪獸的這個時間和另外的移動的時間要達到同步

（是以我WA了= =）

比較推薦的做法是用優先隊列進行BFS，用時間作為優先的比較，按時間從小到大不斷pop出來尋找下一個位置；

同時用pre數組記錄目前頂點的前驅頂點的橫縱坐标，記錄第一次搜到該點時它的前驅頂點，當最後輸出時從(0,0)開始輸出目前位置的前驅頂點（是以bfs是從終點到起點的）

是以過程是這樣的：

從(n-1,m-1)開始bfs，走到下一個可行頂點(x,y)記錄pre[x][y]=(n-1,m-1)

遇到有怪獸的地方隻要把time增加再push進去即可（如果後來的時間比打怪獸的這條路小，那自然會優先到前面去）

直到走到(0,0)，輸出總時間後，列印路徑：

pre[0][0]得到的(x,y)即是到達(0,0)前的那一步，pre[x][y]即是到達(x,y)前的那一步……依次類推，直到(n-1,m-1)

中間有怪獸的地方循環一下即可

如果沒有可到達終點的路徑就自動執行完循環到達函數最後，輸出另一條語句即可

發現此類的題都愛用結構體并且的确友善了很多

是以pair要漸漸不用了嗎~

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
const int N=;
struct node {
    int x,y;
    int time;
    node(int x,int y,int time):x(x),y(y),time(time) {}
    node() {}
};
bool operator<(node a,node b) {//小的時間在top來不斷使用 
    return a.time>b.time;
}
struct Pre {
    int px,py;
} pre[N][N];
int n,m;
char map[N][N];
int vis[N][N];
int dx[]= {,,-,};
int dy[]= {,-,,};
void bfs(int x,int y) {
    priority_queue<node> q;

    if(map[x][y]!='.') q.push(node(x,y,map[x][y]-'0'));

    else q.push(node(x,y,));

    vis[x][y]=;

    pre[x][y].px=-;//标記結束結點 

    while(!q.empty()){
        node first=q.top();
        q.pop();
        if(first.x==&&first.y==){
            int ans=first.time;
            int t=;
            printf("It takes %d seconds to reach the target position, let me show you the way.\n",ans);

            while(pre[first.x][first.y].px!=-){
                int prex=pre[first.x][first.y].px;
                int prey=pre[first.x][first.y].py;
                printf("%ds:(%d,%d)->(%d,%d)\n",t++,first.x,first.y,prex,prey);
                if(map[prex][prey]!='.'){
                    for(int i=;i<map[prex][prey]-'0';i++){
                        printf("%ds:FIGHT AT (%d,%d)\n",t++,prex,prey);
                    }
                }
                first.x=prex,first.y=prey;
            }

            return ;

        }
        for(int i=;i<;i++){
            node next;
            next.x=first.x+dx[i],next.y=first.y+dy[i],next.time=first.time+;

            if(!vis[next.x][next.y]&&next.x>=&&next.x<n&&next.y>=&&next.y<m&&map[next.x][next.y]!='X'){       

                vis[next.x][next.y]=;
                if(map[next.x][next.y]!='.') next.time+=(map[next.x][next.y]-'0');

                pre[next.x][next.y].px=first.x;//記錄第一次搜到的前驅結點
                pre[next.x][next.y].py=first.y;
                q.push(next);
            }
        }
    }
    puts("God please help our poor hero.");

}
int main() {

    while(~scanf("%d %d",&n,&m)) {
        memset(vis,,sizeof(vis));
        for(int i=; i<n; i++) {

            scanf("%s",map[i]);
        }
        bfs(n-,m-);
        puts("FINISH");
    }
    return ;
}