【题解】BFS—迷宫问题(1)
【题目描述】
一个5*5的矩阵，矩阵内用0，1显示。其中，0是路，表示这个点可以走，1是墙表示这个点不可以走。
问，从给定的矩阵中从左上角到右下角最少需要走多少步？
注：题目保证有解（不存在左上角和右下角为1的情况）
【输入描述】
一个5*5的矩阵
【输出描述】
一行，表示最少要走多少步？
【样例输入】
0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
【样例输出】
8
【题目分析】
我们假设把终点设定为数字9，这样便于我们判断。
我们可以把走过的数组用flag数组标记一下。或者把走过的点变为5。（本题采用这个方法，为了更清楚的显示出变化过程）
我们找到数字9（终点）就停止。
先到达的点一定是最短路径
注意，题目并没有让你输出最短路径，只是记录最少走出多少步，所以题目中没有用到记录每一个点的前趋数组（结构体）。
【过程】
上面的过程可以用下列代码表示：
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int Map[6][6]; //定义地图大小
int dir[4][2]= {1,0,-1,0,0,-1,0,1}; //定义方向
int n,m,ans;
struct node
{
int x,y,step;
} now,nextt; //保存走步
int BFS(int x,int y)
{
queue<node>q;
int xx,yy,zz;
Map[x][y]=6; //走过初始点
now.x=x;
now.y=y;
now.step=0;
q.push(now); //从当前点开始
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=0; i<4; i++) //遍历四个方向
{
xx=now.x+dir[i][0];
yy=now.y+dir[i][1]; //走一步
if(xx>=1&&xx<=5&&yy>=1&&yy<=5&&Map[xx][yy]!=1&&Map[xx][yy]!=6) //可以走
{
nextt.x=xx;
nextt.y=yy;
nextt.step=now.step+1; //步数加一
Map[now.x][now.y]=6; //走过一个点
if(Map[xx][yy]==9) //到达终点
return nextt.step;
q.push(nextt);
}
// for(int i=0; i<5; i++){ //打印地图
// for(int j=0; j<5; j++)
// cout << Map[i][j];
// cout << endl;
// }
// cout << endl;
}
}
return -1; //走不过去
}
int main()
{
for(int i=1; i<=5; i++) //输入地图
for(int j=1; j<=5; j++)
cin >> Map[i][j];
Map[5][5]=9; //定义终点
ans=BFS(1,1);
cout << ans<< endl;
return 0;
}大部分的做法都跟dfs一样，除了队列的操作，那么一块来看看，队列在这中间都做了哪些操作。
q.push(now) 将一开始的点入到队列里面。 然后当队列不为空的时候开始循环 （1）将队列队首元素赋值给now，然后将队首元素弹出 （2）以now点为基础，遍历四个方向，如果某个方向的点可以走，则记录下这个方向，标记并把这个点放到队列中。 （3）如果到达终点，则返回结果（step）
如何做到一圈一圈的搜索呢？其实就是
now=q.front(); //读取队首元素 q.pop(); //删除队首元素
每次把元素队首元素删除，然后把新的节点放入到队列中。
整个过程的可以用下面的图来记录前后的访问关系（假设访问每次访问方向都是上下左右）
那么，如果这个题目要求改成：输出最短的路径呢？
比较简单的方法就是用一个数组专门记录成立的点的前趋。但是这个题目成立的点都是坐标。那么我们要定义一个二维数组(结构体)pre，用来记录前趋。
那么在代码中便是
pre[xx][yy]=now (此时now可以理解为上一个点或者当前点。next是下一个点)
当我们程序执行完毕后，我们通过下面的for循环打印出pre数组。
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
cout<<"("<<pre[i][j].x<<" "<<pre[i][j].y<<" "<<")";
}
cout<<endl;
}
可以看出，（5，5）点的前趋点是（4，5）点。而（4，5）点的前趋是（3，5）点，依次类推，可以根据前趋列表求出所有的路径。
这里我们用递归的方式实现。
那么输出最短路径的方法：
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int Map[6][6]; //定义地图大小
int dir[4][2]= {1,0,-1,0,0,-1,0,1}; //定义方向
int n,m,ans;
struct node
{
int x,y,step;
} now,nextt; //保存走步
node pre[10][10];
int BFS(int x,int y)
{
queue<node>q;
int xx,yy,zz;
Map[x][y]=6; //走过初始点
now.x=x;
now.y=y;
now.step=0;
q.push(now); //从当前点开始
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=0; i<4; i++) //遍历四个方向
{
xx=now.x+dir[i][0];
yy=now.y+dir[i][1]; //走一步
if(xx>=1&&xx<=5&&yy>=1&&yy<=5&&Map[xx][yy]!=1&&Map[xx][yy]!=6) //可以走
{
nextt.x=xx;
nextt.y=yy;
nextt.step=now.step+1; //步数加一
Map[now.x][now.y]=6; //走过一个点
pre[xx][yy]=now; //记录前趋(当前这个点 xx,yy 的前趋是个结构体now，)
//cout<<now.x<<","<<now.y<<endl;
if(Map[xx][yy]==9) //到达终点
return nextt.step;
q.push(nextt);
}
// for(int i=0; i<5; i++){ //打印地图
// for(int j=0; j<5; j++)
// cout << Map[i][j];
// cout << endl;
// }
// cout << endl;
}
}
return -1; //走不过去
}
//递归输出路径
void print(int x,int y){
if(x==1 && y==1){
return;
}
cout<<"("<<pre[x][y].x<<" "<<pre[x][y].y<<" "<<")";
print(pre[x][y].x,pre[x][y].y);
}
int main()
{
for(int i=1; i<=5; i++) //输入地图
for(int j=1; j<=5; j++)
cin >> Map[i][j];
Map[5][5]=9; //定义终点
ans=BFS(1,1);
cout << ans<< endl;
print(5,5);//输出(从结果开始递归)
// for(int i=1;i<=5;i++){
//
// for(int j=1;j<=5;j++){
// cout<<"("<<pre[i][j].x<<" "<<pre[i][j].y<<" "<<")";
// }
// cout<<endl;
// }
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
