AcWing 844. 走迷宫
原题链接
简单
作者:
王小强
,
2021-01-24 15:05:00
,
所有人可见
,
阅读 236
BFS Template. Time Complexity: $O(N * M)$
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 105;
int grid[N][N];
using P = pair<int, int>;
static constexpr int dirs[] { 0, -1, 0, 1, 0 };
int bfs(int sx, int sy, int m, int n) {
queue<P> q;
q.emplace(sx, sy);
grid[sy][sx] = 1; // mark as visited
int steps = 0;
while (not q.empty()) {
size_t sz = q.size();
while (sz--) {
const auto [x, y] = q.front(); q.pop();
if (x == n && y == m) return steps;
for (int i = 0; i < 4; ++i) {
const int nx = x + dirs[i], ny = y + dirs[i + 1];
if (nx == 0 || ny == 0 || nx > n || ny > m || grid[ny][nx])
continue;
q.emplace(nx, ny);
grid[ny][nx] = 1; // mark as visted;
}
}
++steps;
}
return -1;
}
int main() {
int m, n;
cin >> m >> n;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) cin >> grid[i][j];
cout << bfs(1, 1, m, n) << endl;
return 0;
}