本文主要是介绍hdu 1072 Nightmare（BFS法和DFS法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1072
题目大意：
0为墙1为路2为起点3为终点4为炸弹
走到任意一个炸弹都可以将所有炸弹重置倒计时6minutes
每走一个位置需要1minutes
问从2到3需要的最少时间
DFS法更快。
BFS法好理解。
思路：
两种方法都需理解一点：
同一个炸弹位置当第二次走到时说明已不是最优解。
BFS法：
处理走到同一个炸弹位置方法：第一次走到炸弹的位置时，将该炸弹设置为0（即墙），将不会再一次走到此处。
然后就是BFS了。
DFS法：
记忆化搜索。
记录走过该点的时间与炸弹剩余爆炸时间。
剪枝：去掉同样走到该位置时所用时间更久和剩余爆炸时间更短的路。
由于BFS法在遍历过程中遍历了更多没必要的路，所以更慢些。
代码如下：
BFS法：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=10;
int G[MAXN][MAXN];
const int nextpos[][2]={{-1,0},{1,0},{0,1},{0,-1}};
int N,M;
struct position
{int x,y;int step;//第几步走到该位置int t;//炸弹剩余爆炸时间
}pos;bool check(int x,int y,int t)
{if(x<0||x>=N||y<0||y>=M||G[x][y]==0||t==0)return false;return true;
}int BFS()
{queue<position>q;q.push(pos);while(!q.empty()){pos=q.front();q.pop();for(int i=0;i<4;i++){position p;p.step=pos.step+1;p.t=pos.t-1;p.x=pos.x+nextpos[i][0];p.y=pos.y+nextpos[i][1];if(check(p.x,p.y,p.t)){if(G[p.x][p.y]==3)return p.step;else if(G[p.x][p.y]==4)//处理：1.炸弹重新计时 2.设置为墙{G[p.x][p.y]=0;p.t=6;}q.push(p);}}}return -1;
}int main()
{int kase;scanf("%d",&kase);while(kase--){scanf("%d%d",&N,&M);for(int i=0;i<N;i++)for(int j=0;j<M;j++){scanf("%d",&G[i][j]);if(G[i][j]==2){pos.x=i;pos.y=j;pos.step=0;pos.t=6;G[i][j]=0;}}printf("%d\n",BFS());}return 0;
}
DFS：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=10;
const int nextpos[][2]={{-1,0},{1,0},{0,-1},{0,1}};
int N,M;
int G[MAXN][MAXN];
int step[MAXN][MAXN];
int time[MAXN][MAXN];
int ans;bool check(int x,int y)//与BFS法的返回值不同
{if(x<1||x>N||y<1||y>M||G[x][y]==0)return true;return false;
}void DFS(int x,int y,int nowt,int bombtime)
{if(check(x,y))return;if(bombtime==0||nowt>=ans)return;if(G[x][y]==3){if(ans>nowt)ans=nowt;return;}if(G[x][y]==4){bombtime=6;}if(step[x][y]<=nowt&&bombtime<=time[x][y]) return;step[x][y]=nowt;time[x][y]=bombtime;for(int i=0;i<4;i++){int nextx=x+nextpos[i][0];int nexty=y+nextpos[i][1];DFS(nextx,nexty,nowt+1,bombtime-1);}
}
int main()
{int kase,startx,starty;scanf("%d",&kase);while(kase--){memset(G,0,sizeof(G));scanf("%d%d",&N,&M);for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){scanf("%d",&G[i][j]);step[i][j]=INT_MAX;time[i][j]=0;if(G[i][j]==2){startx=i;starty=j;}}ans=INT_MAX;step[startx][starty]=0;DFS(startx,starty,0,6);if(ans==INT_MAX)printf("%d\n",-1);elseprintf("%d\n",ans);}return 0;
}
这篇关于hdu 1072 Nightmare（BFS法和DFS法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
