最简单的BFS走迷宫问题

原题目链接:https://www.luogu.com.cn/problem/T279759?contestId=88579

题目背景
人生辗转几十年，今天学长终于遇到了他的喜欢的女孩...

题目描述
在一个阴雨连绵的夜晚，学长在路上走着的时候遇到了他喜欢的女孩，女孩正在路灯下等待雨停，而你恰好拿着伞，并且温柔的学长想要将女孩尽快送回家，现在请你为告诉学长最快回到家要走多远。

输入格式
第一行输入两个整数n,m，表示地图的行数和列数。

下面n行每行m个字符并用空格隔开表示地图，其中0表示可以行走的路，1表示墙壁或积水无法行走。

坐标（1,1）左上角表示学长和女孩当前的位置，坐标（n,m）右下角表示女孩的家，且起点和终点保证为0。

输出格式
输出一行表示学长最短要走多远才能把女孩送到家， 如果无法送到则输出-1

输入输出样例
输入 #1复制
3 3
0 0 0
1 0 0
1 0 0
输出 #1复制
4
输入 #2复制
3 3
0 1 1
1 1 1
1 1 0
输出 #2复制
-1
说明/提示
2<=n,m<=100; 学长认为这是件大事，所以就作为压轴的。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef pair<int,int> PII;
 4 const int N=110;
 5 //bfs:走迷宫问题,只适用与权重都为1的图
 6 int n,m;
 7 int g[N][N];//存储图
 8 int d[N][N];//存储每个位置都走过了没,以及走到这个位置走了几步
 9 PII q[N*N];//队列,一般bfs都是需要队列的
10 
11 int bfs(){
12     int hh=0,tt=0;//hh代表队列头,tt代表队列尾
13     q[0]={0,0};
14     memset(d,-1,sizeof(d));//看这个点曾经走过没有,-1代表没有走
15     d[0][0]=0;//因为从左上角开始走,所以认为左上角是走过的
16     int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//存储的是向量
17     while(hh<=tt){
18         auto t=q[hh++];//每次取出队头,这里感觉吃力的话那就说明前面的队列没有学的滚瓜烂熟
19         for(int i=0;i<4;i++){//通过向量的方式遍历上下左右四个格子
20             int x=t.first+dx[i];
21             int y=t.second+dy[i];
22             if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1){//下一格可以走的条件
23                 d[x][y]=d[t.first][t.second]+1;//到达这一格子的步数是上一个格子加1
24                 q[++tt]={x,y};//进队列,通过队列把整个迷宫给遍历一遍,找到最短路径
25             }
26         }
27     }
28     return d[n-1][m-1];//返回到达最后一个格子所需要步数
29 }
30 int main(){
31     cin>>n>>m;//这里n,m都是全局变量
32     for(int i=0;i<n;i++){//输入图
33         for(int j=0;j<m;j++){
34             cin>>g[i][j];
35         }
36     }
37     cout<<bfs()<<endl;
38     return 0;
39 }
40 /*
41   cin:
42   5 5
43   0 1 0 0 0
44   0 1 0 1 0
45   0 0 0 0 0
46   0 1 1 1 0
47   0 0 0 1 0
48   cout:
49   8
50 */

考察内容:最简单的BFS走迷宫问题