AcWing 844. 走迷宫
原题链接
简单
作者:
-_8
,
2020-09-15 14:18:32
,
所有人可见
,
阅读 359
#include <cstdio>
#include <queue>
#define x first
#define y second
using namespace std;
const int N = 110;
int n,m;
int s[N][N],d[N][N];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
typedef pair<int,int>PII;
queue<PII>q;
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)scanf("%d",&s[i][j]), d[i][j] = -1;
d[1][1] = 0;
q.push({1,1});
while(q.size()){
PII nst = q.front();
q.pop();
if(nst.x == n && nst.y == m){
printf("%d",d[nst.x][nst.y] );
break;
}
for(int i = 0; i < 4; ++i){
int nx = nst.x + dx[i], ny = nst.y + dy[i];
if(nx < 1 || nx > n || ny < 1 || ny > m || s[nx][ny] || d[nx][ny] != -1)continue;
q.push({nx,ny});
d[nx][ny] = d[nst.x][nst.y] + 1;
}
}
return 0;
}