AcWing 189. 乳草的入侵
原题链接
简单
作者:
爱卢娜
,
2021-01-20 18:16:15
,
所有人可见
,
阅读 444
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 110;
char g[N][N];
int dist[N][N];
PII q[N * N];
int ans;
int n, m, sx, sy;
void bfs(int x, int y)
{
int hh = 0, tt = 0;
q[hh] = { x, y };
memset(dist, -1, sizeof dist);
dist[x][y] = 0;
while(hh <= tt)
{
auto t = q[hh ++];
for(int i = t.x - 1;i <= t.x + 1;i ++)
for(int j = t.y - 1;j <= t.y + 1;j ++)
{
if(i == t.x && j == t.y) continue;
if(i < 0 || i >= n || j < 0 || j > m || dist[i][j] != -1 || g[i][j] != '.') continue;
dist[i][j] = dist[t.x][t.y] + 1;
q[++ tt] = { i, j };
ans = max(ans, dist[i][j]);
}
}
}
int main()
{
cin >> m >> n >> sx >> sy;
for(int i = 0;i < n;i ++) cin >> g[i];
bfs(n - sy, sx - 1);
cout << ans << endl;
return 0;
}