题目分析:
- 求连通块个数和最大连通块
- 十进制转换为四位数的二进制,从左到右依次表示WNES(西北东南)
代码如下:
#include<iostream>
#include<queue>
using namespace std;
#define x first
#define y second
#define pii pair<int,int>
#define el endl
const int N = 55;
int n,m;
int g[N][N];
bool st[N][N];
int dx[4] = {0,-1,0,1};
int dy[4] = {-1,0,1,0};
int bfs(int sx,int sy){
queue<pii> q;
q.push({sx,sy});
st[sx][sy] = true;
int area = 0;
while(q.size()){
pii t = q.front();
q.pop();
area ++;
for(int i = 0; i < 4; i ++ ){
int a = t.x + dx[i],b = t.y + dy[i];
if(a < 0 || a > n - 1 || b < 0 || b > m - 1) continue;
if(st[a][b] || (g[t.x][t.y] >> i) & 1) continue;
st[a][b] = true;
q.push({a,b});
}
}
return area;
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i ++ )
for(int j = 0; j < m; j ++ )
cin >> g[i][j];
int cnt = 0,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<<el<<area<<el;
return 0;
}