AcWing 844. 走迷宫
原题链接
简单
作者:
yihang6
,
2024-03-25 21:46:11
,
所有人可见
,
阅读 2
思路
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=101;
int g[N][N];//记录图信息,0/1
int d[N][N];//记录到起点的距离
int n,m;
int bfs(){
queue<pair<int,int>> q;
q.push({1,1});//起点放入
while(!q.empty()){//不为空时
pair<int,int> h=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 xx=h.first+dx[i],yy=h.second+dy[i];
if(d[xx][yy]==-1&&g[xx][yy]==0){//如果这个点没访问过d为-1,并且可通行g为0
q.push({xx,yy});//扩展结点
d[xx][yy]=d[h.first][h.second]+1;//更新到起点的距离
}
}
}
return d[n][m];//由于一圈一圈向外扩展,第一次扩展到时的d就是最小值
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
d[i][j]=-1;//-1表示还没有经过这个点
}
}
d[1][1]=0;//起点初始化,距离为0
cout<<bfs();
return 0;
}