AcWing 1098. 城堡问题(bfs,floodfill,对输入的处理
原题链接
简单
注意对输入的处理即可,经典bfs,根据二进制哪一位上有1判断有没有墙
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=1010;
int w[N][N];
int st[N][N];
typedef pair<int, int> PII;
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>w[i][j];
}
}
queue<PII> q;
int res=0;
int area=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(st[i][j]==0)
{
q.push({i,j});
res++;
int s=1;
st[i][j]=res;
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
while(q.size())
{
auto t=q.front();
q.pop();
for(int k=0;k<4;k++)
{
int a=t.first+dx[k];
int b=t.second+dy[k];
if(a>=1 && a<=n &&b>=1 &&b<=m &&((w[t.first][t.second]>>k&1)==0) && st[a][b]==0)
{
st[a][b]=1;
q.push({a,b});
s++;
}
}
}
area=max(area,s);
//break;
}
}
}
cout<<res<<endl;
cout<<area;
return 0;
}