AcWing 1099. 仙岛求药
原题链接
简单
作者:
纪年
,
2021-04-23 13:00:06
,
所有人可见
,
阅读 336
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 310;
typedef pair<int, int> PII;
int n, m;
char g[N][N];
int dist[N][N];
int bfs(int a, int b)
{
memset(dist, -1, sizeof dist);
dist[a][b] = 0;
queue<PII> q;
q.push({a, b});
int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};
while (q.size())
{
auto t = q.front();
q.pop();
for (int i = 0; i < 4; i ++ )
{
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] != '#' && dist[x][y] == -1)
{
dist[x][y] = dist[t.first][t.second] + 1;
q.push({x, y});
}
}
}
for (int i = 0; i < m; i ++ )
for (int j = 0; j < n ; j ++ )
if (g[i][j] == '*')
return dist[i][j];
}
int main()
{
while (true)
{
cin >> m >> n;
if (m == 0 && n == 0) break;
int x, y;
for (int i = 0; i < m; i ++ )
for (int j = 0; j < n; j ++ )
{
cin >> g[i][j];
if (g[i][j] == '@')
{
x = i, y = j;
}
}
cout << bfs(x, y) << endl;
}
return 0;
}