AcWing 1099. 仙岛求药
原题链接
简单
作者:
王小强
,
2021-01-29 22:00:59
,
所有人可见
,
阅读 369
BFS Algorithm
#include <iostream>
#include <queue>
using namespace std;
using P = pair<int, int>;
static constexpr int dirs[] { 0, -1, 0, 1, 0 };
const int N = 310;
char g[N][N];
int m, n, sx, sy;
int bfs() {
queue<P> q;
q.emplace(sx, sy);
g[sy][sx] = '#'; // mark as seen
int steps = 0;
while (not q.empty()) {
size_t sz = q.size();
while (sz--) {
const auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dirs[i], ny = y + dirs[i + 1];
if (nx < 0 || ny < 0 || nx == n || ny == m || g[ny][nx] == '#')
continue;
if (g[ny][nx] == '*') return steps + 1;
q.emplace(nx, ny);
g[ny][nx] = '#'; // mark as seen
}
}
++steps;
}
return -1;
}
int main() {
while (cin >> m >> n, m || n) {
for (int y = 0; y < m; ++y)
for (int x = 0; x < n; ++x) {
cin >> g[y][x];
if (g[y][x] == '@') sx = x, sy = y;
}
cout << bfs() << endl;
}
return 0;
}