算法分析
可以先求出海平面未上升前的连通块个数,然后将它容斥掉连通块内部存在某个格子满足它四周都是陆地的连通块,可以用 std::set
来维护这种连通块,因为我用的是并查集来找连通块,所以这里 std::set
维护的就是没有淹没的连通块的根节点
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
struct UnionFind {
vector<int> d;
UnionFind(int n = 0): d(n, -1) {}
int find(int x) {
if (d[x] < 0) return x;
return d[x] = find(d[x]);
}
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (d[x] > d[y]) swap(x, y);
d[x] += d[y];
d[y] = x;
return true;
}
bool same(int x, int y) {
return find(x) == find(y);
}
int size(int x) {
return -d[find(x)];
}
};
const int di[] = {0, 1, 0, -1};
const int dj[] = {1, 0, -1, 0};
int main() {
int n;
cin >> n;
vector<string> s(n);
rep(i, n) cin >> s[i];
int ans = 0;
int m = n*n;
UnionFind uf(m);
rep(i, n)rep(j, n) {
if (s[i][j] != '#') continue;
ans++;
rep(d, 4) {
int ni = i+di[d], nj = j+dj[d];
if (ni < 0 or ni >= n or nj < 0 or nj >= n) continue;
if (s[ni][nj] != '#') continue;
int v = i*n+j, u = ni*n+nj;
if (uf.same(v, u)) continue;
uf.unite(v, u);
ans--;
}
}
set<int> st;
rep(i, n)rep(j, n) if (s[i][j] == '#') {
int v = i*n+j;
int r = uf.find(v);
if (st.count(r)) continue;
bool ok = true;
rep(d, 4) {
int ni = i+di[d], nj = j+dj[d];
if (ni < 0 or ni >= n or nj < 0 or nj >= n) continue;
ok &= s[ni][nj] == '#';
}
if (ok) {
ans--;
st.insert(r);
}
}
cout << ans << '\n';
return 0;
}