大概花了一天的时间来写这道题，看了别人的题解，其实没有什么不对劲，就是自己的方法并不是太协调
早上做出来的程序其实整体上已经很不错了，但还有一点不正确的地方，就是记录路径的方式不正确。
不知算不算是水题，反正做了很久了···
1.这道题的路径记录要注意怪兽出现的地方：当前如果出项怪兽，那么记录的方法要记录在当前点还是每个下个搜索点
2.输出路径的时候可以采取递归的方式，这道题其实递归输出最好了。
3.看别人的题解都是用了优先队列，可能对于这个题目的数据，没有用优先队列对于时间复杂度的影响不大，都是0ms秒过的
4，下面代码用普通队列进行搜索，记录方式有很多，这里用二维转一维方法记录，稍微复杂，个人习惯。
贴一下自己的代码
#include <stdio.h> #include <map> #include <queue> using namespace std; int maz[110][110],vis[110][110],pat[110][110]; int tim[110][110],fat[110][110]; int ans,n,m; const int dx[]={1,0,-1,0}; const int dy[]={0,-1,0,1}; int is_ok(int x,int y){ if(x<0 || x>=n || y<0 || y>=m || maz[x][y]=='X') return 0; return 1; } int bat(int x,int y) { if(maz[x][y]=='.') return 0; return maz[x][y] - '0'; } bool flag=0; bool bfs() { flag=0; memset(tim,0,sizeof(tim)); memset(vis,0,sizeof(vis)); memset(fat,0,sizeof(vis)); memset(pat,0,sizeof(pat)); queue<int>q; q.push(0); vis[0][0]=1; pat[0][0]=0; tim[0][0]=0; fat[0][0]=-1; int x,y,vs; while(!q.empty()) { int tn = q.front();q.pop(); x=tn/m,y=tn%m; if(x == n-1 && y == m-1) { ans = pat[x][y]; tim[x][y] = bat(x,y); flag=1; } for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; vs = bat(nx,ny); if(is_ok(nx,ny)) { if(vis[nx][ny]) { if(pat[nx][ny] > pat[x][y] + 1 + vs) { pat[nx][ny] = pat[x][y] + 1 + vs; q.push(nx*m+ny); tim[nx][ny] = vs; fat[nx][ny] = x * m + y; } } else { vis[nx][ny]=1; pat[nx][ny] = pat[x][y] + 1 + vs; q.push(nx*m+ny); tim[nx][ny] = vs; fat[nx][ny] = x * m + y; } } } } return flag; } int count = 0; int path[10000]; void pth(int k) { int x=k/m,y=k%m; int fk = fat[x][y]; if(fat[x][y]==-1) return; int nx=fk/m,ny=fk%m; pth(fk); printf("%ds:(%d,%d)->(%d,%d) ",pat[nx][ny]+1,nx,ny,x,y); if(pat[x][y]-pat[nx][ny]>1) { int Tim=pat[x][y]-pat[nx][ny]-1; for(int i=1;i<=Tim;i++) printf("%ds:FIGHT AT (%d,%d) ",pat[nx][ny]+i+1,x,y); } } void prt(){ for(int i=0;i<n;i++) for(int j=0;j<m;j++) printf("%d%c",pat[i][j],j==m-1?' ':' '); } #include <stdlib.h> int main() { // freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); char ch[120]; while(scanf("%d %d",&n,&m)!=EOF) { count = 0; memset(maz,0,sizeof(maz)); for(int i=0;i<n;i++) { scanf("%s",ch); for(int j=0;j<m;j++) { maz[i][j] = ch[j]; } } flag = bfs(); if(!flag) puts("God please help our poor hero. FINISH"); else { printf("It takes %d seconds to reach the target position, let me show you the way. ", ans); //prt(); pth((n-1)*m+m-1); puts("FINISH"); } } return 0; }
附加一下测试代码，可以在起点加一个怪兽看当前的结果，今天找个一个ac程序竟然不处理起点的怪兽也是可以的。
/* 5 6 .XX.1. ..X.2. 2...X. ...XX. XXXXX. 5 6 .XX.1. ..X.2. 2...X. ...XX. XXXXX1 5 6 2XX... .1X.2. 2...X. ...XX. XXXXX1 5 6 2.1.X. X.X.3. .X..X. X..XX. XX...3 5 6 ..X.X. X.X..4 X...X. .3491. ...... */