当前位置 博文首页 > weixin_45770392的博客：c++迷宫问题bfs/dfs
【例8.4】迷宫问题 【深搜参考程序】
如下图所示，给出一个N*M的迷宫图和一个入口、一个出口。
编一个程序，打印一条从迷宫入口到出口的路径。这里黑色方块的单元表示走不通（用-1表示），白色方块的单元表示可以走（用0表示）。只能往上、下、左、右四个方向走。如果无路则输出“no
way.”。
下面给出两种解决方法分别是用dfs和bfs解决
以（0，0）为入口，（3，8）为出口
1,dfs
#include<iostream>
#include<cstring>
using namespace std;
int n,m,dis=100000;
int a[100][100]={0};
int vis[100][100]={0};
int h[4][2]={1,0,0,1,-1,0,0,-1};
struct node
{
int x,y;
}s[100],t[100];
int top=0;
int step=0;
void dfs(int x,int y,int sum)
{
int i;
for(i=0;i<4;i++)
{
int hx=x+h[i][0];
int hy=y+h[i][1];
if(a[hx][hy]==0&&!vis[hx][hy]&&hx<m&&hx>=0&&hy<n&&hy>=0)
{
vis[hx][hy]=1;
s[top++].x=hx,s[top-1].y=hy;
if(hx==3&&hy==8&&dis>sum)
{
for(int j=0;j<top;j++)
t[j]=s[j];
dis=sum;
step=top;
}
else
dfs(hx,hy,sum+1);
vis[hx][hy]=0;
top--;
}
}
}
int main()
{
cin>>m>>n;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>a[i][j];
vis[0][0]=1;
s[top].x=0,s[top].y=0;
dfs(0,0,1);
for(int i=0;i<step;i++)
cout<<"("<<t[i].x<<","<<t[i].y<<") ";
cout<<endl;
cout<<dis<<endl;
return 0;
} 2,bfs
#include<iostream>
#include<cstring>
using namespace std;
int n,m;
int a[100][100]={0};
int vis[100][100]={0};
int h[4][2]={1,0,0,1,-1,0,0,-1};
struct node
{
int x,y;
}s[100];
int b[100]={0};//记录前驱下标
int dis[100][100]={0};
void print(int f)
{
if(b[f]!=-1)
print(b[f]); //递归输出结果坐标
cout<<"("<<s[f].x<<","<<s[f].y<<") ";
}
void bfs(int x,int y)
{
int head=0,tail=0;
int i,j;
b[head]=-1;
s[tail++].x=x,s[tail-1].y=y;
while(head!=tail)
{
x=s[head].x,y=s[head].y;
for(i=0;i<4;i++)
{
int hx=x+h[i][0];
int hy=y+h[i][1];
if(a[hx][hy]==0&&!vis[hx][hy]&&hx<m&&hx>=0&&hy<n&&hy>=0)
{
vis[hx][hy]=1;
b[tail]=head;
s[tail++].x=hx,s[tail-1].y=hy;
dis[hx][hy]=dis[x][y]+1;
if(hx==3&&hy==8) //本题以出口为坐标(3,8)
{
print(tail-1);
return;
}
}
}
head++;
}
cout<<"no way"<<endl;
}
int main()
{
cin>>m>>n;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>a[i][j];
vis[0][0]=1;
bfs(0,0);
cout<<endl<<dis[3][8]<<endl; //本题以迷宫入口为 (0,0)出口为(3，8)
return 0;
} 
