AcWing
1233. 全球变暖
连通块问题，用DFS或BFS都可以：遍历一个连通块（找到这个连通块中所有的#，并标记已经搜过，不用再搜）；再遍历下一个连通块…；遍历完所有连通块，统计有多少个连通块。
回到题目，若岛中有个陆地（称为高地），它周围都是陆地，那么这个岛不会被完全淹没。
用DFS或BFS搜出有多少个岛（连通块），并且在搜索时统计那些没有高地的岛（连通块）的数量，就是答案。
因为每个像素点只用搜一次且必须搜一次，所以时间复杂度是$O(n^2)$.
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1010;
char m[N][N];
bool visited[N][N], flag; // 单块陆地是否被访问、岛屿是否会被淹没
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
void dfs(int x, int y){
visited[x][y] = true;
int adj = 0; // 四个邻接位的陆地总数
for(int i = 0; i <= 3; i ++){
int xx = x + dx[i], yy = y + dy[i];
if(m[xx][yy] == '#') adj ++;
if(xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
if(m[xx][yy] == '.') continue;
if(visited[xx][yy]) continue;
dfs(xx, yy);
}
if(adj == 4) flag = false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 0; i <= n - 1; i ++) cin >> m[i];
int cnt = 0; // 被淹没的岛屿数量
for(int i = 1; i <= n - 2; i ++)
for(int j = 1; j <= n - 2; j ++)
if(m[i][j] == '#' && !visited[i][j]){
flag = true;
dfs(i, j);
if(flag) cnt ++;
}
cout << cnt;
return 0;
}