问题描述
给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。 最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。 请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。 数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。 输入格式 第一行包含两个整数 n 和 m。 接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。 输出格式 输出一个整数，表示从左上角移动至右下角的最少移动次数。 数据范围 1≤n,m≤100 输入样例： 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 原题链接：https://www.acwing.com/problem/content/846/
参考代码(C++版本)
#include <iostream> #include <queue> #include <cstring> #include <algorithm> using namespace std; typedef pair<int,int> PII; const int N = 110; int n,m; int g[N][N],d[N][N]; //存放地图的数组和存放距离的数组 queue<PII> q; int bfs() { memset(d,-1,sizeof d);//使用<cstring>中的库函数memset快速初始化数组 d[0][0] = 0;//标记点(0,0)已经走过了 q.push({0,0}); //放置的偏移量数组 int dx[] ={-1,0,1,0},dy[] = {0,1,0,-1}; //当队列不为空，执行下述操作 while(q.size()) { auto t = q.front(); //取出队头元素 q.pop();//已获得队头信息，队头可以出队了 //对四个方向进行探索 for(int i = 0; i < 4;i++) { //利用向量数组获得四个方向的坐标 int x = t.first+dx[i],y = t.second+dy[i]; if(x >= 0 && x < n && y >= 0 &&y <m && g[x][y] == 0&& d[x][y] == -1) { d[x][y] = d[t.first][t.second]+1;//更新现在的点(x,y)到起点的距离 q.push({x,y});//将新的坐标入队 } } } return d[n-1][m-1];//返回起点到顶点的宽搜结果 } int main() { cin >> n >>m; for(int i = 0; i < n;i++) for(int j = 0;j< m;j++) cin >> g[i][j]; cout << bfs() <<endl; return 0; }
知识储备
宽度优先搜索(Breadth-first search,BFS)
一点闲话
宽度优先搜索也是一种常用的搜索方式之一，和它一起耳熟能详的是深度优先搜索(DFS),都是从某个状态出发，探索所有可以到达的状态
BFS的搜索模式
宽度优先搜索总是先搜索距离初始状态近的状态。也就是说，它是按照这样的顺序进行搜索的，开始状态——>只需转移1次就可以到达的所有状态——>只需转移2次就可以到达的所有状态——>…。对于同一个位置，宽度优先搜索只会经过它一次，以后再碰到它便不会再检索它。
BFS依赖的数据结构
宽度优先搜索不同于深度优先搜索，它是一层一层的进行遍历，因此需要用到的是先入先出的队列
BFS的用武之地
BFS可以用于处理一下问题:
第一类问题：可达性问题。从结点A出发，有前往结点B的路径吗？
第二类问题：最短路问题。从结点A出发，前往结点B的哪条路最短？
由于按照层次逐层进行搜索、遍历，宽度优先搜索时按照距开始状态由近及远的顺序进行搜索，也就常常用来处理最短路、最少操作等问题。
注意：宽度优先搜索只能解决每条边的权值是相同的最短路径问题。其他情况的最短路问题需要使用专门的最短路算法，比如：Dijkstra算法、Bellman-Ford算法等等。这些算法后续我也会持续更出对它们的理解和总结的喔~🎉🎉🎉
解题思路
BFS的运作流程
前提铺垫：使用数组d[]记录个当前点v到起点s的距离
将起点s放入队列Q中(访问)
只要Q不空，循环执行下述操作
从Q中取出顶点u进行访问(访问结束)
将与u相邻的未访问的顶点v放入Q，同时将d[v]更新为d[u] +1
逻辑思路讲解
1.输入：创建地图
cin >> n >>m; for(int i = 0; i < n;i++) for(int j = 0;j< m;j++) cin >> g[i][j];
2.调用bfs()函数
cout << bfs() <<endl;
实现宽搜的bfs()函数
1，前戏——初始化整个距离数组
memset(d,-1,sizeof d);//使用的是<cstring>库中的memset函数，按照字节对传入的数组全部初始化为-1 d[0][0] = 0;//表示点(0,0)已经走过了
2， 将起点s放入队列Q中(访问)
q.push({0,0});
3，只要Q不空，循环执行下述操作===> 取队头，拓展队头
int dx[] ={-1,0,1,0},dy[] = {0,1,0,-1}; while(q.size()) { auto t = q.front(); q.pop(); for(int i = 0; i < 4;i++) { int x = t.first+dx[i],y = t.second+dy[i]; if(x >= 0 && x < n && y >= 0 &&y <m && g[x][y] == 0&& d[x][y] == -1) { d[x][y] = d[t.first][t.second]+1; q.push({x,y}); } } }
难点剖析
最难处理的应该是循环体中的逻辑怎么安排
首先，按照bfs运作流程取出队头.这里使用了c++的关键字auto,它会自动判断返回值类型，偷懒省事必备喔
获得队头信息以后，这个队头就可以出队了，使得下一个信息可以来到队头的位置被获取
auto t = q.front(); q.pop()
然后，将与u相邻的未访问的顶点v放入Q 也就是拓展队头，判断队头可以向走到哪些位置。此处取巧使用了向量数组来表示4个移动的方向。将获取后的新坐标放到if判断里，判断其是否越界，是否是可以探索的，是否被探索过。假如都没有，那就占据这个点，也就是将其入队，同时将d[v]更新为d[u] +1
for(int i = 0; i < 4;i++) { int x = t.first+dx[i],y = t.second+dy[i]; if(x >= 0 && x < n && y >= 0 &&y <m && g[x][y] == 0&& d[x][y] == -1) { d[x][y] = d[t.first][t.second]+1; q.push({x,y}); } }
关于方向向量数组
如图，可以将一个坐标点进行抽象，那么它在x轴上能活动的区域，按照顺时针记录，是{-1,0,1,0}。对于y一样可以这种记录，即{0,1,0,-1}。
使用向量数组可以简化我们的代码，对于四个方向的探索就可以不用麻烦的写if判断
举一反三——信息学奥赛一本通-T1255
给定一个 n×n 的二维数组，如下所示： int maze[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, }; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。 数据保证至少存在一条从左上角走到右下角的路径。 输入格式 第一行包含整数 n。 接下来 n 行，每行包含 n 个整数 0 或 1，表示迷宫。 输出格式 输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。 按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)，右下角坐标为 (n−1,n−1)。 数据范围 0≤n≤1000 输入样例： 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 输出样例： 0 0 1 0 2 0 2 1 2 2 2 3 2 4 3 4 4 4
参考代码(C++版本)
#include <iostream> #include <cstring> #include <queue> #include <algorithm> #include <cstdio> using namespace std; typedef pair<int,int> PII; const int N = 1010; int n; int g[N][N]; PII prev_num[N][N]; void bfs(int sx,int sy) { queue<PII> q; //入队 q.push({sx,sy}); int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1}; memset(prev_num,-1 ,sizeof prev_num); //当队列不为空 while(q.size()) { //取队头 PII t = q.front(); q.pop(); //拓展队头 for(int i = 0;i < 4;i++) { int a = t.first+dx[i],b = t.second+dy[i]; if(a< 0 || a >= n || b < 0 || b >= n) continue;//越界 if(g[a][b]) continue;//墙 if(prev_num[a][b].first != -1) continue; //加到队列 q.push({a,b}); //记录上个状态的位置 prev_num[a][b] = t; } } } int main() { scanf("%d",&n); for(int i = 0; i <n;i++) for(int j = 0;j < n;j++) scanf("%d",&g[i][j]); bfs(n-1,n-1); PII end(0,0); while(true) { printf("%d %d\n",end.first,end.second); if(end.first == n-1 && end.second == n-1) break; end = prev_num[end.first][end.second]; } return 0; }
解题思路
这道迷宫问题和走迷宫几乎是一样的，思路是一样的，用宽度优先搜索一层一层的去查找，第一次搜索到的终点就是最短路径。要求我们输出这段路径。
道理谁都懂，随口就能生动形象的描述出来，从这个点走到哪个点，再转一下…问题怎么用代码实现出来了？
我们来手动模拟一下bfs探索的过程，先取出队头，然后咱们站在队头的位置，眺望四方，康康哪里可以走了？喔~~~ 那里可以走，好的，走上去,记录下当前的位置，再探索。按照这种流程，我们可以开一个数组，记录当前这个点(x,y)是从哪个点走过来的。
详细剖析
记录数据
typedef pair<int,int> PII; PII prev_num[N][N]; // 记录数据的伪代码如下： prev_num[x][y] = 探索前的坐标
//记录上个状态的位置 prev_num[a][b] = t;
1。涉及的stl容器：pair(数对)是将2个数据组合成一组数据。pair的实现是一个结构体，主要的两个成员变量first和second，分别存储两个数据。因为我们要输出的是一组坐标，那么用数对pair来记录会让我们，如鱼得水
2.关于prev_num[x][y] = 探索前的点,有小伙伴读起来可能比较蒙，what’s this ?！各位看官，可这种理解喔
现在有一个二维矩阵，矩阵的类型是存放一组int型变量的数对，矩阵的名字是prev_num。现在让矩阵中位置是(x,y)的这块空间存放探索前的坐标t(这个坐标肯定也是数对类型的啦~)
输出数据
经过一番倒腾，数据终于记录进去了，现在怎么输出这个二维数组了？注意喔，正是因为它是二维数组，所以不能很暴力的直接两个for循环输出结果。因为其他没有用到的位置也会被遍历输出。
这里就出现了比较巧妙的一点，bfs搜索的时候，倒着搜索回去。那我存放的点就是从起点(0,0)逐步逐步的到达终点，这样我们就可以正向遍历这段路径了
bfs(n-1,n-1);//倒着搜回去 PII end(0,0);//创建一个PII类型的变量end，初始化为(0,0) while(true) { printf("%d %d\n",end.first,end.second); if(end.first == n-1 && end.second == n-1) break; end = prev_num[end.first][end.second]; }
