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; //preint a,b; //nowint 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數組標記的話，那么我們就無法更新到達某一個點的花費的最小值了，這里解決的方案是：我們在加入隊列時，只有當當前節點被重新更新了，我們才將它放在隊列中。反之，我們就沒有必要加入進去了。

算法結束時，我們記錄的是最短路前驅。

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的HDU1026 Ignatius and the Princess I（深度优先搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。