题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1026。
分析：
申明：这题我是参考了一大牛犀利的方法AC的——采用坐标标号化。我自己的太垃圾不好意思贴出来。 此题中我们使用buf[]数组保存每一秒（有的时间段不走在打怪）的father结点，如果相邻两秒的fa结点相同那么证明英雄此时在打怪，如果不同那么英雄此时一定面对的是‘.’路径（对于输出路径，这个方法应该是最好的了）。这道题中，我们使用——（列*行坐标+列坐标）来表示当前点（即将这个点变成标号）。当然标号坐标化也很简单。
该题使用优先队列来处理数据。
#include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<algorithm> using namespace std; #define init(a,what) memset(a,what,sizeof(a)) #define read freopen("zx.in","r",stdin) #define write freopen("zx.out","w",stdout) const int MAXN=100+10; const int MAXM=10000+10; class ARR { public: int x, y, step; friend bool operator < (const ARR &a,const ARR &b) { return a.step>b.step; } }; ARR arr,cur; int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int row,column,ans,pr,fa[MAXM],tim[MAXM],buf[MAXM]; char map[MAXN][MAXN]; bool inmap(int x,int y) { if(x>=0&&x<row&&y>=0&&y<column) return true; return false; } void output() { int temp=pr, len=ans; for(int i=0;i<tim[temp];i++) buf[len--]=temp; while(fa[temp]!=-1)//设置起点的fa结点为-1 { temp=fa[temp]; for(int j=0;j<tim[temp];j++) buf[len--]=temp;//如果在两步内所用的时间相等，证明此地有怪兽 } buf[len]=0; for(int i=0;i<ans;i++) { int x=buf[i]/column, y=buf[i]%column; int ix=buf[i+1]/column, iy=buf[i+1]%column; if(x==ix && y==iy) printf("%ds:FIGHT AT (%d,%d)/n",i+1,x,y); else printf("%ds:(%d,%d)->(%d,%d)/n",i+1,x,y,ix,iy); } } bool bfs() { priority_queue<ARR>q; init(tim,0); init(fa,0); init(buf,0); arr.x=0, arr.y=0, arr.step=0; fa[0]=-1, tim[0]=1; while(!q.empty()) q.pop(); q.push(arr); map[0][0]='X'; while(!q.empty()) { cur=q.top(); q.pop(); if(cur.x==row-1 && cur.y==column-1) { ans=cur.step, pr=cur.x*column+cur.y; return true; } for(int i=0;i<4;i++) { arr.x=cur.x+direction[i][0], arr.y=cur.y+direction[i][1]; if(inmap(arr.x,arr.y) && map[arr.x][arr.y]!='X') { if(map[arr.x][arr.y]=='.') arr.step=cur.step+1; else arr.step=cur.step+1+map[arr.x][arr.y]-'0'; map[arr.x][arr.y]='X'; q.push(arr); fa[arr.x*column+arr.y]=cur.x*column+cur.y; tim[arr.x*column+arr.y]=arr.step-cur.step; } } } return false; } int main() { //read, write; while(scanf("%d%d",&row,&column)!=EOF) { for(int i=0;i<row;i++) for(int j=0;j<column;j++) cin>>map[i][j]; //printf("%c/n",map[row-1][column-1]); if(bfs()) { printf("It takes %d seconds to reach the target position, let me show you the way./n",ans); output(); } else printf("God please help our poor hero./n"); printf("FINISH/n"); } return 0; }
