AcWing 189. 乳草的入侵
原题链接
简单
作者:
赐荒
,
2025-04-21 13:07:24
· 新疆
,
所有人可见
,
阅读 1
#include<iostream>
#include<queue>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
char g[N][N];
int vis[N][N];
int n,m;
PII start;
int bfs()
{
memset(vis,-1,sizeof vis);
queue<PII>q;
q.push(start);
vis[start.x][start.y]=0;
int dx[]={0,1,1,1,0,-1,-1,-1};
int dy[]={1,1,0,-1,-1,-1,0,1};
int res = 0;
while(!q.empty())
{
PII t = q.front();
q.pop();
for(int i = 0;i<8;i++)
{
int x = t.x+dx[i],y = t.y+dy[i];
if(x<1||x>n||y<1||y>m) continue;
if(vis[x][y]!=-1) continue;
if(g[x][y]=='*') continue;
vis[x][y]=vis[t.x][t.y]+1;
res = max(res,vis[x][y]);
q.push({x,y});
}
}
return res;
}
int main()
{
cin>>m>>n>>start.y>>start.x;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
cin>>g[i][j];
}
}
cout<<bfs()<<endl;
}