AcWing 844. 走迷宫
原题链接
简单
作者:
qgc123
,
2021-11-29 15:36:14
,
所有人可见
,
阅读 156
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 105;
int a[N][N], n, m, ans = 0xfffffff, fx[4] = { 0, 0, 1, -1 }, fy[4] = { 1, -1, 0, 0 },
xx[N * N], yy[N * N], idx, d[N][N], head = -1;
void bfs() {
xx[idx] = 1;
yy[idx++] = 1;
d[1][1] = 0;
while (head < idx) {
for (int i = 0; i < 4; i++) {
int x = fx[i] + xx[head+1], y = fy[i] + yy[head+1];
//cout << x << " " << y << endl;
if (x >= 1 && x <= n && y >= 1 && y <= m && !d[x][y] && !a[x][y]) {
//cout << x << " " << y << endl;
d[x][y] = d[xx[head+1]][yy[head+1]] + 1;
xx[idx] = x;
yy[idx++] = y;
}
}
head++;
}
cout << d[n][m] << endl;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
bfs();
return 0;
}