代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII; //图中每个点需要二维坐标定位
#define x first //简化坐标的写法
#define y second
const int N = 1010;
char g[N][N]; //存储图的信息
bool st[N][N]; //存储图中每个点的状态————是否被访问过
int n;
int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
void bfs(int x, int y, int& sum, int& bound) {
queue<PII> q; //实现 bfs 的队列
st[x][y] = true;//第一块土地置为已访问并进队
q.push({x, y});
while(!q.empty()) {
PII t = q.front(); //每次取出队头元素
q.pop();
bool is_bound = false; //当前土地快标记为未淹没
sum++; //土地块数量+1
for(int i = 0; i < 4; i++) { //遍历上下左右四个相邻的地方
int xx = t.x + dx[i], yy = t.y + dy[i];
if(xx < 0 || xx >= n || yy < 0 || yy >= n) continue; //越界
else if(st[xx][yy]) continue; //已访问
else if(g[xx][yy] == '.') { //相邻海边
is_bound = true; //置为淹没
continue;
}
st[xx][yy] = true; //不被淹没则进队并置为已访问
q.push({xx, yy});
}
if(is_bound) bound++; //被淹没则淹没土地数量+1
}
return;
}
int main() {
scanf("%d", &n); //读入图的信息
for(int i = 0; i < n; i++) scanf("%s", g[i]);
int res = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(g[i][j] == '#' && !st[i][j]) { //遍历每个未访问过的连通块
int sum = 0, bound = 0; //sum为连通块土地数量, bound为淹没土地数量
bfs(i, j, sum, bound);
if(sum == bound) res++; //当 sum == bound 时, 整个连通块被淹没, res+1
}
}
}
cout << res << endl;
return 0;
}