优先队列+BFS+保存路径
额，先记录前驱，再用栈输出路径，其他的，都快成模板了，最近打得很熟，就是输出的时候，一些小错误改了半天ORZ
#include<iostream> #include<queue> #include<algorithm> #include<stack> using namespace std; char map[101][101]; int vis[101][101],n,m,mins; bool rescue; int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; struct node { int x,y,cnt; node(int _x=0,int _y=0,int _cnt=0):x(_x),y(_y),cnt(_cnt){}; friend bool operator <(const node &a, const node &b) { return a.cnt>b.cnt; } }; node f[101][101]; void bfs() { node t; t.x=1;t.y=1;t.cnt=0; priority_queue<node> Q; Q.push(t); vis[1][1]=1; while(!Q.empty()) { node b=Q.top(); Q.pop(); if(b.x==n&&b.y==m) { rescue=1; mins=b.cnt; return; } for(int k=0;k<4;k++) { int i=b.x+dir[k][0]; int j=b.y+dir[k][1]; if(i<=n&&i>0&&j<=m&&j>0&&!vis[i][j]&&map[i][j]!='X') { vis[i][j]=1; f[i][j].x=b.x;f[i][j].y=b.y;f[i][j].cnt=b.cnt+1;//记录前驱 if(map[i][j]=='.') Q.push(node(i,j,b.cnt+1)); else Q.push(node(i,j,b.cnt+(map[i][j]-'0')+1)); } } } } void print() { stack<node> S; node temp=f[n][m]; S.push(node(n,m,mins)); while(temp.x!=1||temp.y!=1) { S.push(temp); temp=f[temp.x][temp.y]; } int t=1; while(!S.empty()) { temp=S.top(); S.pop(); if(map[temp.x][temp.y]=='.') printf("%ds:(%d,%d)->(%d,%d)\n",t++,f[temp.x][temp.y].x-1,f[temp.x][temp.y].y-1,temp.x-1,temp.y-1); else { printf("%ds:(%d,%d)->(%d,%d)\n",t++,f[temp.x][temp.y].x-1,f[temp.x][temp.y].y-1,temp.x-1,temp.y-1); int k=map[temp.x][temp.y]-'0'; while(k--) printf("%ds:FIGHT AT (%d,%d)\n",t++,temp.x-1,temp.y-1); //printf("%ds:(%d,%d)->(%d,%d)\n",t++,temp.x,temp.y,S.top().x,S.top().y); } } printf("FINISH\n"); return ; } int main() { while(cin>>n>>m) { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) cin>>map[i][j]; } memset(vis,0,sizeof(vis)); rescue=0; bfs(); if(rescue) printf("It takes %d seconds to reach the target position, let me show you the way.\n",mins); else {printf("God please help our poor hero.\nFINISH\n");continue;} print(); } return 0; }转载于:https://www.cnblogs.com/nanke/archive/2011/08/02/2125537.html
相关资源：数据结构—成绩单生成器