BFS模板：844. 走迷宫

给定一个 n×mn×m 的二维整数数组，用来表示一个迷宫，数组中只包含 00 或 11，其中 00 表示可以走的路，11 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1)(1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m)(n,m) 处，至少需要移动多少次。

数据保证 (1,1)(1,1) 处和 (n,m)(n,m) 处的数字为 00，且一定至少存在一条通路。

输入格式

第一行包含两个整数 nn 和 mm。

接下来 nn 行，每行包含 mm 个整数（00 或 11），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n,m≤1001≤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

思路

1.宽度优先搜索：和深度优先搜索有区别，深度优先搜索是选择一条路径走到尽头，然后再回溯，宽度优先搜索是类似于一圈一圈往外寻找可能的路径，然后寻找到一条最短路径

2.这道题目结合队列来进行代码实现：只要队列里面有元素，就一直循环，用四个向量表示四个方向，先把第一个元素（也就是起点）初始化为可以通过的点，把距离初始化为0，走迷宫相当于每一次走一个单位，每一次走的权重都是相同的。根据题意，地图里面是0可以通过，是1就不可以通过，距离的二维数组在最开始的时候就被初始化为了-1，每一个坐标都是-1，只要某一次使用了那个坐标，那个坐标所对应的距离就不再是-1，就不可以再被使用了，这样子就可以保证我们寻找到的是最短路径，只要有一条路径走到了终点，终点坐标对应的距离就不再是-1，不能被使用，也就是说其他路径永远走不到终点

3.我们最后返回终点到起点的距离即可

代码

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;const int N=110;
typedef pair<int,int> PII;
int n,m;
int g[N][N],d[N][N];int bfs()
{queue<PII> q;memset(d,-1,sizeof d);d[0][0]=0;q.push({0,0});while(q.size()){auto t=q.front();q.pop();int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};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});}}}return d[n-1][m-1];
}int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%d",&g[i][j]);printf("%d\n",bfs());return 0;
}