AcWing 844. 走迷宫
原题链接
简单
作者:
满目星河_0
,
2021-03-31 12:32:24
,
所有人可见
,
阅读 204
带注释(超详细)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int p[N][N],d[N][N];
//p[N][N]用来表示输入的地图,d[N][N]表示走了多少步。
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
//表示上下左右四个方向移动
int m,n;
int bfs(){
queue<PII> q; //初始化队列,队列中的每个元素都是(x,y)坐标的形式。
q.push({0,0});//起始点为(0,0)
d[0][0]=0; //原点的步数为0
while(!q.empty()){//如果队列不空,代表没有遍历完整张地图。
auto t=q.front();//返回队头元素
q.pop(); //并把队头元素弹出
for(int i=0;i<4;i++){
int x=t.first+dx[i];
int y=t.second+dy[i];
if(x>=0&&x<m&&y>=0&&y<n&&p[x][y]==0&&d[x][y]==-1){
//如果不越界并且要求下一步是0。
//注:这里必须要保证d[x][y]==-1代表没有走过这个点,不然不能得到最短路径。
d[x][y]=d[t.first][t.second]+1; //步数加1
//注:这里必须是在前一步的基础上加1,相当于一个累加的过程。不能是d[x][y]
//本身加1。
//printf("%d",d[x][y]);
q.push({x,y});//走过的点加入路径
}
}
}
return d[m-1][n-1];//返回右下角的步数就是最短步数
}
int main(){
cin>>m>>n;
memset(d,-1,sizeof(d));
//将d数组初始化为-1,表示没有走过。
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin>>p[i][j];
}
}
cout<<bfs();
return 0;
}