以上图片摘自百度图片
放假无聊，去逛了下acwing,一进去就给我推了道难题（早知道就去逛b站了），叫我走迷宫，看到这道题我思考了一阵，发现可以用之前学的BFS（广度优先搜索）大招来解决，bug时刻…
本着下面这个原则
while(有bug){ 改bug if（accept）break; }
最终成功的走出了迷宫。
我们首先来看一下这道经典的走迷宫题吧，可以在acwing上搜索走迷宫，找到本题额
最后来看看我是如何走出迷宫的！
#include<bits/stdc++.h> using namespace std; int n,m; typedef pair<int,int> PII; //用来存点，用pair方便点点 const int N=110; //数据范围 int g[N][N],d[N][N];// g数组装整个图， d数组表示某点到原点的距离 int bfs(){ queue<PII> q; q.push({0,0});//首先起点入队 memset(d,-1,sizeof d);//将最开始的所有点到起点的距离都设置为-1 d[0][0]=0;//起点到起点的距离设置为0, int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}; /*方向数组，随便向那个方向扩展都得行， 我的是上(x不变，y会加1)右（x会加1，y不变）下（x不变，y会减1）左（x会减1，y不变）*/ while(!q.empty()){ auto t = q.front();//取出队首元素 q.pop();//队首出队 for(int i=0;i<4;i++){//向4个方向扩展 // x,y 为扩展后的， t装的是拓展前的坐标 int x=t.first+dx[i]; int y=t.second+dy[i]; //满足边界条件，拓展的点的位置没有障碍，在之前没有被访问过（距离为-1就表示没访问过） 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];//最终 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()<<"\n";//输出结果 }
