1 条题解
-
0
按高度从小到大地顺序考虑每个位置,用并查集维护连通性。具体来讲,假设当前考虑到的高度为 ,对每个取出来的位置,其相邻位置如果高度不超过 或者是外界(简单起见,把外界也看成一个结点)就合并连通块。
这样一来,所有高度 且不与外界相邻的位置都是可以继续积水的(至少增加 ),因为其四周肯定有比他高的位置会阻挡。具体实现见代码。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; const LL mod = 1e9 + 7; const int N = 10005; int a[105][105]; vector<int> b[N]; int p[N]; int sz[N]; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } void Union(int x, int y) { x = find(x), y = find(y); if (x != y) { p[x] = y; sz[y] += sz[x]; } } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &a[i][j]); b[a[i][j]].push_back(i * m + j); } } for (int i = 0; i <= n * m; i++) { p[i] = i; sz[i] = 1; } sz[n * m] = 0; int ans = 0; int cnt = 0; for (int i = 1; i <= 10000; i++) { for (auto t : b[i]) { int x = t / m, y = t % m; cnt++; for (int j = 0; j < 4; j++) { int tx = x + dx[j]; int ty = y + dy[j]; if (tx >= 0 && tx < n && ty >= 0 && ty < m) { if (a[tx][ty] <= a[x][y]) Union(t, tx * m + ty); } else { Union(t, n * m); } } } ans += cnt - sz[find(n * m)]; } cout << ans << endl; return 0; }
- 1
信息
- ID
- 4601
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者