原题题干
解题思路
并查集求连通块数量,这种题的核心一般都是思考如何去维护$setcnt$。
此题需逆向思考,想象潮水褪去、岛逐渐浮出水面的过程,即先处理海平面高的情况,因为这样就是慢慢往图中加点;如果是按题意正着做,浮在水面上的越来越少,意味着要删点,相比于加点要麻烦。
每加一个点,先不管三七二十一,都假设连通块数量加一,然后再判断这个点四周有没有之前已经加进来的点,如果有,且它们还不在同一个连通块内,就把它们合并,连通块数量减一。
此外还考察了行和列下标都从$0$开始的二维坐标映射成一维坐标。
很常规,很综合性的一道好题,个人认为是学习并查集必做题。
具体代码
#include <bits/stdc++.h>
using namespace std;
typedef struct Grid
{
int x, y, h;
bool operator<(const Grid &it) const //重载小于运算符
{
return h < it.h;
}
} node;
const int N = 1010, M = 1e5 + 10;
int n, m, k, setcnt;
bool st[N * N];
int p[N * N], y[M], ans[M];
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int get(int x, int y) //坐标映射
{
return x * m + y;
}
void add(node u) //把一个点加进图中
{
setcnt++; //先不管三七二十一,连通块数量加一
st[get(u.x, u.y)] = true; //表明已加入图中
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
for (int i = 0; i < 4; i++) //遍历上下左右四个方向
{
int tx = u.x + dx[i];
int ty = u.y + dy[i];
if (tx >= 0 && tx < n && ty >= 0 && ty < m && st[get(tx, ty)])
//如果相邻的上下左右有之前已经加进来的点
{
int pa = find(get(u.x, u.y));
int pb = find(get(tx, ty));
if (pa != pb) //若还不在同一连通块内,就现在将它们合并
{
setcnt--;
p[pa] = pb;
}
}
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
memset(st, false, sizeof st);
vector<node> q; //专门开个vector存这些点是为了排序,然后方便加点
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
int h;
cin >> h;
q.push_back({i, j, h});
}
}
cin >> k;
for (int i = 0; i < k; i++)
cin >> y[i];
sort(q.begin(), q.end()); //将点排序,方便加点
for (int i = 0; i < n * m; i++)
p[i] = i;
int pos = q.size() - 1;
setcnt = 0;
for (int i = k - 1; i >= 0; i--)
{
while (q[pos].h > y[i]) //这一年能浮出来的点都加入地图
{
add(q[pos]);
pos--;
}
ans[i] = setcnt;
}
for (int i = 0; i < k; i++)
cout << ans[i] << ' ';
cout << '\n';
}
return 0;
}