首页 > 代码库 > DFS与BFS应用于小哈迷宫
DFS与BFS应用于小哈迷宫
DFS与BFS均能胜任此途：
#include <iostream>#include <fstream>#include <cstring>#include <vector>#include <queue>#include <stack>#include <algorithm>#include <cmath>using namespace std;#define loop(i,n) for(int i=0;i<(n);i++)#define loop2(i,n) for(int i=1;i<=(n);i++)int n,m,p,q,xmin=9999;int a[51][51],book[51][51];int next[4][2]={{0,1}, {1,0}, {0,-1}, {-1,0}};struct note{ int x,y,f,s;}que[2501];void bfs(int x,int y){ int tx,ty,flag=0; int head=1,tail=1; book[x][y]=1;//往队列插入迷宫入口坐标 que[tail].x=x; que[tail].y=y; que[tail].s=0; que[tail].f=0; tail++; while(head<tail) { for(int k=0;k<4;k++) { //计算下一个点的坐标 tx=que[head].x+next[k][0]; ty=que[head].y+next[k][1]; if(tx<1 || tx>n || ty<1 ||ty>m) //判断是否越界 continue; if(a[tx][ty]==0 && book[tx][ty]==0) //判断是否障碍物或已经在路径中 {
//把这个点标记为已经走过。注意宽搜每个点只入队一次，所以和深搜不同，不需要将book数组还原 book[tx][ty]=1; que[tail].x=tx;//插入新的点到队列中 que[tail].y=ty;
que[tail].f=head; //因为这个点是从head扩展出来的，所以它的父亲是head，本题目不需要求路径，因此本句可省略。 que[tail].s=que[head].s+1; //步数是父亲的步数+1 tail++; }
//目标点到了，停止扩展，任务结果，退出循环 if(tx==p && ty==q) {
//不要写反了 flag=1; break; } } if(flag==1) break; head++; //千万不要忘记，当一个点扩展结束后，head++才能对后面进行扩展 } xmin=que[tail-1].s; }void dfs(int x,int y,int step){ int tx,ty; if(x==p && y==q) { if(step<xmin) xmin=step; return; } for(int k=0;k<4;k++) { tx=x+next[k][0]; ty=y+next[k][1]; if(tx<1 || tx>n || ty<1 || ty>m) continue; if(a[tx][ty]==0 && book[tx][ty]==0) { book[tx][ty]=1; dfs(tx,ty,step+1); book[tx][ty]=0; } }}void test(){ freopen("maze.in","r",stdin); //freopen("maze.out","w",stdout); int startx,starty; cin>>n>>m; loop2(i,n) loop2(j,m) cin>>a[i][j]; cin>>startx>>starty>>p>>q; //book[startx][starty]=1; //dfs(startx,starty,0); bfs(startx,starty); cout<<xmin<<endl; }int main () { test(); return 0;}
test data:
5 40 0 1 00 0 0 00 0 1 00 1 0 00 0 0 11 1 4 3
DFS与BFS应用于小哈迷宫
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。