# 迷宫求解非递归 DFS BFS(应用栈和队列)

+关注继续查看

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define Maze_size 100 //定义迷宫最大值
class Maze
{
public:
char Maze_map[Maze_size][Maze_size];
bool Maze_map_bj[Maze_size][Maze_size];
int stack[Maze_size][2],top;//栈 栈顶指针
int queue[Maze_size][3],base,qtop;//队列 0 1存坐标 2记录路径 对首指针 队尾指针
int length,wide;//迷宫长,宽(竖,横)
int startx,starty;//起点坐标
int step[4][2];
Maze();//初始化迷宫
void input();//从键盘输入
bool DFS();//利用栈深度优先遍历
bool BFS();//利用队列广度优先遍历
void outputDFSmap();//输出深度优先遍历路径
void outputBFSmap();//输出广度优先遍历路径
};

Maze::Maze()//初始化
{
length=wide=0;
startx=starty=0;
step= {{0,1},{0,-1},{1,0},{-1,0}};
top=0;
}

void Maze::input()//输入
{
do
{
cout<<"input length and wide of maze(length>0,wide>0)"<<endl;
cin>>length>>wide;
}
while(length<=0||wide<=0);
cout<<"input maze"<<endl;
for(int i=0; i<length; i++)
for(int j=0; j<wide; j++)
{
cin>>Maze_map[i][j];
if(Maze_map[i][j]=='S')
startx=i,starty=j;
}
cout<<"input end"<<endl;
}

bool Maze::DFS()
{
top=0;
memset(Maze_map_bj,0,sizeof(Maze_map_bj));
stack[++top][0]=startx,stack[top][1]=starty;
Maze_map_bj[startx][starty]=1;
while(top!=0)
{
int x=stack[top][0],y=stack[top][1];
for(int i=0; i<4; i++)
if(Maze_map[x+step[i][0]][y+step[i][1]]=='E')
return 1;
bool flag=0;
for(int i=0; i<4; i++)
if(Maze_map[x+step[i][0]][y+step[i][1]]=='.'&&!Maze_map_bj[x+step[i][0]][y+step[i][1]])
{
stack[++top][0]=x+step[i][0],stack[top][1]=y+step[i][1];
Maze_map_bj[x+step[i][0]][y+step[i][1]]=1;
flag=1;
break;
}
if(flag)
continue;
top--;
}
return 0;
}

void Maze::outputDFSmap()
{
if(!DFS())
{
cout<<"maze bu neng zou = = "<<endl;
return ;
}
char newmap[Maze_size][Maze_size];
for(int i=0; i<length; i++)
for(int j=0; j<wide; j++)
newmap[i][j]=Maze_map[i][j];
for(int i=2; i<=top; i++)
newmap[stack[i][0]][stack[i][1]]='*';
cout<<"DFS:"<<endl;
for(int i=0; i<length; i++)
for(int j=0; j<wide; j++)
{
cout<<newmap[i][j];
if(j==wide-1)
cout<<endl;
}
cout<<endl;
}

bool Maze::BFS()
{
base=0,qtop=1;
memset(Maze_map_bj,0,sizeof(Maze_map_bj));
queue[base][0]=startx,queue[base][1]=starty,queue[base][2]=0;
Maze_map_bj[startx][starty]=1;
while(base!=qtop)
{
int x=queue[base][0],y=queue[base][1];
for(int i=0; i<4; i++)
{
if(Maze_map[x+step[i][0]][y+step[i][1]]=='E')
return 1;
if(Maze_map[x+step[i][0]][y+step[i][1]]=='.'&&!Maze_map_bj[x+step[i][0]][y+step[i][1]])
{
queue[qtop][0]=x+step[i][0],queue[qtop][1]=y+step[i][1];
queue[qtop][2]=base;
qtop++;
Maze_map_bj[x+step[i][0]][y+step[i][1]]=1;
}
}
base++;
}
return 0;
}

void Maze::outputBFSmap()
{
if(!BFS())
{
cout<<"maze bu neng zou = = "<<endl;
return ;
}
char newmap[Maze_size][Maze_size];
for(int i=0; i<length; i++)
for(int j=0; j<wide; j++)
newmap[i][j]=Maze_map[i][j];
while(base!=0)
{
newmap[queue[base][0]][queue[base][1]]='*';
base=queue[base][2];
}
cout<<"BFS:"<<endl;
for(int i=0; i<length; i++)
for(int j=0; j<wide; j++)
{
cout<<newmap[i][j];
if(j==wide-1)
cout<<endl;
}
cout<<endl;
}
int main()
{
Maze a;
a.input();
a.outputBFSmap();
a.outputDFSmap();
return 0;
}


BFS算法模板与练习
BFS算法模板与练习
7 0

18 0

31 0
java实现图的深度优先搜索(DFS)和广度优先搜索(BFS)

179 0
【数据结构和算法】图的遍历（深度优先遍历DFS与广度优先遍历BFS）
【数据结构和算法】图的遍历（深度优先遍历DFS与广度优先遍历BFS）
46 0

75 0
【31. 走迷宫（BFS）】
## 思路 - 用 g[n][m] 存储地图，d[n][m] 存储起点到 n,m 的距离。 - 从起点开始广度优先遍历地图。 - 当地图遍历完，就求出了起点到各个点的距离，输出d[n][m]即可。
72 0

31 0
+关注