AcWing 1098. 城堡问题
原题链接
简单
作者:
minux
,
2020-05-20 11:43:59
,
所有人可见
,
阅读 442
c++ bfs&位运算判定
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int, int> PII;
const int N=55;
const int dirs[4][2]={{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
int G[N][N];
bool vis[N][N];
queue<PII> q;
int n, m;
int main(){
memset(vis, 0x00, sizeof vis);
memset(G, 0x00, sizeof G);
cin>>n>>m;
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
cin>>G[i][j];
function<int(int, int)> bfs=[&](int i, int j){
int area=1;
vis[i][j]=true;
q.push({i, j});
while(!q.empty()){
int x=q.front().fi;
int y=q.front().se;
q.pop();
for(int d=0; d<4; ++d){
if(!(G[x][y]>>d&0x01)){
int nx=x+dirs[d][0];
int ny=y+dirs[d][1];
if(0<=nx && nx<n && 0<=ny && ny<m && !vis[nx][ny]){
vis[nx][ny]=true;
area++;
q.push({nx, ny});
}
}
}
}
return area;
};
int ans=0, area=0;
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
if(!vis[i][j]){
area=max(area, bfs(i, j));
ans++;
}
cout<<ans<<endl;
cout<<area<<endl;
return 0;
}