【题解】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）
整个过程的可以用下面的图来记录前后的访问关系（假设访问每次访问方向都是上下左右）
那么，如果这个题目要求改成：输出最短的路径呢？
比较简单的方法就是用一个数组专门记录成立的点的前趋。但是这个题目成立的点都是坐标。那么我们要定义一个二维数组(结构体)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; }(adsbygoogle = window.adsbygoogle || []).push({});