算法1:宽搜连通块的过程中标记() $O(n)$
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
string g[N];
int n;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
bool bfs(int sx, int sy) {
queue<PII> q;
q.push({sx, sy});
g[sx][sy] = '@'; //标记被遍历
int res = 1;
while (q.size()) {
PII t = q.front();
q.pop();
//默认该点四个方向都没有挨着水
bool f = 1;
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 >= n || g[a][b] == '@') continue;
if (g[a][b] == '.') f = 0; //挨着水域了,
if (g[a][b] == '#') {
g[a][b] = '@';
q.push({a, b});
}
}
if (f) res = 0;//不会消失
}
return res;
}
int main() {
cin >> n;
for (int i = 0; i < n; ++ i) cin >> g[i];
//遇到# 宽搜一遍,标记出挨着.的个数 以及总个数 减法
int res = 0;
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
if (g[i][j] == '#')
res += bfs(i, j);
cout << res;
return 0;
}
算法2:深搜标记() $O(n)$
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
string g[N];
int n, f; //f用来标记深搜过程中,该连通块是否全部消失了
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
bool st[N][N];
void dfs(int x, int y) {
st[x][y] = 1;//标记被访问了
bool fxy = 1; //默认标记x-y点周围没有水
for (int i = 0; i < 4; ++ i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (g[nx][ny] == '.') fxy = 0;
if (st[nx][ny] || g[nx][ny] == '.') continue;
dfs(nx, ny);
}
if (fxy) f = 0;//fxy点不会被淹没,所有该岛不会消失,f标记0
}
int main() {
cin >> n;
for (int i = 0; i < n; ++ i) cin >> g[i];
//遇到#深搜一下
int res = 0; //统计一下消失岛的数量
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
if (!st[i][j] && g[i][j] == '#') {
f = 1; //默认是会消失的,只要有一个不会淹没就不会消失
dfs(i, j);
res += f;
}
cout << res;
return 0;
}