2018-5-2
其实广搜还是比较容易想到的，但是这道题目相对复杂了一点，需要注意的是： 1）我们可能在那点需要花个时间打个怪兽 2）我们需要记录走过的路径并倒序输出（倒序输出可以用深度优先搜索实现）
#include<iostream> #include<cstring> #include<queue> #define inf 0x3f3f3f3f using namespace std; const int N = 100; char x[N+1][N+1]; int rx[N*N+1],ry[N*N+1]; int m,n; int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1}; struct pre{ int p,q; //pre int a,b; //now int c; //cost }y[N+1][N+1]; bool isvalid(int i,int j){ if (i<0||j<0||i>n-1||j>m-1) return false; return true; } void display(){ if (y[n-1][m-1].c==inf){ cout<<"God please help our poor hero."<<endl; } else{ cout<<"It takes "<<y[n-1][m-1].c<<" seconds to reach the target position, let me show you the way."<<endl; int x1=n-1,x2=m-1,i=1,j; rx[0]=x1;ry[0]=x2; while (!(x1==0&&x2==0)){ rx[i]=y[x1][x2].p; ry[i]=y[x1][x2].q; x1=rx[i]; x2=ry[i]; i++; } int t=1,pp; for (j=i-1;j>=0;j--){ if (x[rx[j]][ry[j]]=='.'||x[rx[j]][ry[j]]=='X') { if (j-1>=0) cout<<t<<"s:("<<rx[j]<<","<<ry[j]<<")->"<<"("<<rx[j-1]<<","<<ry[j-1]<<")"<<endl; t++; } else{ pp=x[rx[j]][ry[j]]-'0'; while (pp){ cout<<t<<"s:FIGHT AT ("<<rx[j]<<","<<ry[j]<<")"<<endl; t++;pp--; } if (j-1>=0) cout<<t<<"s:("<<rx[j]<<","<<ry[j]<<")->"<<"("<<rx[j-1]<<","<<ry[j-1]<<")"<<endl; t++; } } } cout<<"FINISH"<<endl; } void init(){ for (int i=0;i<n;i++){ for (int j=0;j<m;j++){ y[i][j].c=inf; y[i][j].a=i; y[i][j].b=j; } } } void bfs(){ init(); int k,ii,jj; queue<struct pre>que; struct pre tmp; tmp.p=0;tmp.q=0;tmp.a=0;tmp.b=0;tmp.c=0; que.push(tmp); while (!que.empty()){ tmp=que.front(); que.pop(); for (k=0;k<4;k++){ ii=tmp.a+dx[k];jj=tmp.b+dy[k]; if (isvalid(ii,jj)&&x[ii][jj]!='X'){ if (x[ii][jj]=='.'){ if (tmp.c+1<y[ii][jj].c){ y[ii][jj].c=tmp.c+1; y[ii][jj].p=tmp.a; y[ii][jj].q=tmp.b; que.push(y[ii][jj]); } }else{ if (tmp.c+x[ii][jj]-'0'+1<y[ii][jj].c){ y[ii][jj].c=tmp.c+x[ii][jj]-'0'+1; y[ii][jj].p=tmp.a; y[ii][jj].q=tmp.b; que.push(y[ii][jj]); } } } } } display(); } int main(){ int i,j; while (cin>>n>>m){ for (i=0;i<n;i++){ for (j=0;j<m;j++){ cin>>x[i][j]; } } bfs(); } return 0; }说一下我的思路：与平时的bfs不同的是，之前只要搜到即是结果，因为我们等同于找到层数最少的，但是这里还可以需要加上打怪兽的时间，我看好多都是用优先队列实现的；还有一个，之前的而言，走过了就不能再走了，但是这里可以还可能往回走，因为我记录了到每一个点所需要的最小值，如果用flag数组标记的话，那么我们就无法更新到达某一个点的花费的最小值了，这里解决的方案是：我们在加入队列时，只有当当前节点被重新更新了，我们才将它放在队列中。反之，我们就没有必要加入进去了。
算法结束时，我们记录的是最短路前驱。
