AcWing 1098. 城堡问题
原题链接
简单
作者:
Value
,
2020-06-24 14:13:24
,
所有人可见
,
阅读 415
#include <iostream>
#include <queue>
using namespace std;
const int N = 60;
int graph[N][N];
bool st[N][N];
int n, m;
typedef pair<int, int> pii;
int dic[4][2] = {
{0, -1}, {-1, 0}, {0, 1}, {1, 0}
};
int bfs(int x, int y){
queue<pii> qu;
qu.push({x, y});
st[x][y] = true;
int area = 0;
while(!qu.empty()){
pii now = qu.front();
qu.pop(); area ++ ;
for(int i = 0; i < 4; i ++ ){
int xx = now.first + dic[i][0];
int yy = now.second + dic[i][1];
if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
if(st[xx][yy]) continue;
if(graph[now.first][now.second] >> i & 1) continue;
qu.push({xx, yy});
st[xx][yy] = true;
}
}
return area;
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i ++ ){
for(int j = 0; j < m; j ++ ){
cin >> graph[i][j];
}
}
int cnt = 0;
int area = 0;
for(int i = 0; i < n; i ++ ){
for(int j = 0; j < m; j ++ ){
if(st[i][j]) continue;
area = max(area, bfs(i, j));
cnt ++ ;
}
}
cout << cnt << endl;
cout << area << endl;
return 0;
}