AcWing 844. 走迷宫
原题链接
简单
作者:
成为一个优秀的人
,
2021-04-14 12:35:22
,
所有人可见
,
阅读 205
#include<iostream>
#include<queue>
#include<cstring>
const int N = 105;
int a[N][N];
int dist[N][N];
int n,m;
using namespace std;
typedef pair<int,int>PII;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
#define x first
#define y second
void bfs(int cx,int cy)
{
queue<PII>q;
q.push({cx,cy});
a[cx][cy]=1; //将起始点赋值为1
while(q.size())
{
PII u=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int l=dx[i]+u.x;
int r=dy[i]+u.y;
if(l>=1&&r>=1&&l<=n&&r<=m&&a[l][r]==0) //满足条件加入队列
{
q.push({l,r});
a[l][r]=1;
dist[l][r]=dist[u.x][u.y]+1;
}
}
}
cout<<dist[n][m]<<endl;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
bfs(1,1);
return 0;
}