AcWing 844. 走迷宫
原题链接
简单
作者:
新鲜的蓝血
,
2021-12-13 21:05:30
,
所有人可见
,
阅读 194
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=110;
typedef pair<int,int> PII;
#define x first
#define y second
int g[N][N];
int d[N][N];//存距离;
int n,m;
int bfs()
{
memset(d,-1,sizeof d); //距离初始化为-1;
queue<PII> q;//设置队列q;
d[0][0]=0;//初始距离为0;
q.push({0,0});
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
while(!q.empty())
{
PII t=q.front();
q.pop();
int i;
for(i=0;i<4;i++)
{
int ix=t.x+dx[i];
int iy=t.y+dy[i];
if(ix>=0&&ix<n&&iy>=0&&iy<m&&g[ix][iy]==0&&d[ix][iy]==-1)
{
d[ix][iy]=d[t.x][t.y]+1;//更新距离;
q.push({ix,iy});
}
}
}
return d[n-1][m-1];
}
int main()
{
scanf("%d%d",&n,&m);
int i,j;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&g[i][j]);//输入地图;
printf("%d",bfs());
return 0;
}