题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1026
题意：输入n，m和一个n*m的矩阵，
.表示通路；
x表示墙；
n表示有一个怪物，消灭它需要n个时间。
求从（0,0）到（n-1，m-1）所需要的最短时间。
如果不存在，照题目格式输出；如果存在，将路径输出。
思路：广搜遍历求出最短路径，并用优先队列优化。
可以用递归逆向遍历出路径（开始没想到）。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; struct Node{ int x,y,step; friend bool operator<(Node a,Node b) { return b.step<a.step; } }; char a[120][120]; int vis[120][120],fx[120][120],blood[120][120]; int n,m,tim,zz[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int bfs() { priority_queue <Node> q; Node tmp; tmp.x=0;tmp.y=0;tmp.step=0; vis[0][0]=-1; q.push(tmp); while(!q.empty()) { Node tmp=q.top(); q.pop(); if(tmp.x==n-1&&tmp.y==m-1) return tmp.step; for(int i=0;i<4;i++) { Node tp; tp.x=tmp.x+zz[i][0]; tp.y=tmp.y+zz[i][1]; if(tp.x<0||tp.x>=n||tp.y<0||tp.y>=m||vis[tp.x][tp.y]==-1) continue; tp.step=tmp.step+1+vis[tp.x][tp.y]; vis[tp.x][tp.y]=-1; fx[tp.x][tp.y]=i+1; q.push(tp); } } return -1; } void Print(int x,int y) { int tx,ty; if(fx[x][y]==0) return ; tx=x-zz[fx[x][y]-1][0]; ty=y-zz[fx[x][y]-1][1]; Print(tx,ty); cout<<tim++<<"s:("<<tx<<","<<ty<<")->("<<x<<","<<y<<")"<<endl; while(blood[x][y]--) cout<<tim++<<"s:FIGHT AT ("<<x<<","<<y<<")"<<endl; } int main(void) { int i,j; while(cin>>n>>m) { memset(fx,0,sizeof(fx)); memset(blood,0,sizeof(blood)); for(i=0;i<n;i++) scanf("%s",a[i]); for(i=0;i<n;i++) for(j=0;j<m;j++) { if(a[i][j]=='.') vis[i][j]=0; else if(a[i][j]=='X') vis[i][j]=-1; else vis[i][j]=a[i][j]-'0',blood[i][j]=vis[i][j]; } int ans=bfs(); if(ans==-1) { cout<<"God please help our poor hero."<<endl; } else { cout<<"It takes "<<ans<<" seconds to reach the target position, let me show you the way."<<endl; tim=1; Print(n-1,m-1); } cout<<"FINISH"<<endl; } return 0; }