AcWing 1098. 城堡问题
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-03-13 09:30:48
,
所有人可见
,
阅读 345
#include <iostream>
using namespace std;
const int N = 55, M = N * N;
typedef pair<int, int> PII;
PII q[M];
int g[N][N];
bool st[N][N];
int n, m;
int bfs(int x, int y) {
int hh = 0, tt = 0;
int area = 0;
//开始的状态, 队列中只有一个元素
q[0] = {x, y};
//此时来标记起点已经走过了
st[x][y] = true;
while (hh <= tt) {
//取出来队头元素
PII t = q[hh ++];
area ++;
//下面来枚举四个方向上是否有墙
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
for (int i = 0; i < 4; i ++) {
int a = t.first + dx[i], b = t.second + dy[i];
//如果没有出界
if (a < 0 || a >= n || b < 0 || b >= m) continue;
//如果此位置已经被遍历过了
if (st[a][b]) continue;
//然后来判断此时是否是联通的
if (g[t.first][t.second] >> i & 1) continue;
//此时表示是可以走到(a, b)位置上的
q[++ tt] = {a, b};
st[a][b] = true;
}
}
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 ++) {
//此时的bfs函数有一个返回值, 就是当前连通块的个数
if (!st[i][j]) {
area = max(area, bfs(i, j));
//此时连通块的个数需要 + 1
cnt ++;
}
}
}
cout << cnt << endl;
cout << area << endl;
return 0;
}