854
迷宮求解非遞歸 DFS BFS(應用棧和隊列)
棧和隊列的應用對迷宮問題求解 沒有遞歸 自己手動建的棧和隊 並且輸出路徑 DFS的路徑就是
棧中的坐標 BFS的路徑在隊又開了一個域存上一層的base值 語言還是用的C++ 感覺比C的封裝性好很多
充分體會了一下DFS一邊比BFS快 但是BFS是最優解而DFS可能不是最優解
#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;
}
最後更新：2017-04-02 22:15:49