题解 SP212 【WATER - Water among Cubes】
龙之吻—水货
2019-03-12 20:59:12
# Water among Cubes
## 题目大意
> 给定一个 $n*m$的场地，每一个格子上有高度为$h_{ij}$长方体，现在突然下雨了，问能存多少水？ form @partychicken
## 解题报告
终于解决了一道历史遗留问题，发现是初始化的锅 QAQ
这题有多组数据，但是并没有告诉我们$t$的大小 QwQ，从SPOJ上的讨论得知这道题 $t$ 的最大值为 $13$ ，考虑到 $n, m \leq 100, h_{ij} \leq 10000$ 加上 $7s$ 的时限，选择直接打暴力！
我们从最低高度扫到最高高度，每次考虑高度为 $H$ 的一层，对于这一层，当且仅当当前格子的 $h_{ij}$ 小于 $H$，并且从当前格子只通过 $h_{ij}$ 小于 $H$ 的格子不会出界的时候，这个格子在当前层是能存住水的。
于是我们吧 $h_{ij} \geq H$ 的格子当作墙，进行一次洪水填充，这样没被洪水淹到且不为墙的格子就是这一层有水的格子。
所以我们可以在 $O(nm)$ 的时间对一层完成答案统计，总时间复杂度 $O(Tnm\max (height_{ij}))$，勉强可过 QwQ。
当然了，这道题的正解显然不是这个暴力，我们可以使用 $heap + BFS$ 在更短的时间复杂度内解决这个问题。~~不过因为忙着补坑并没有去思考这个做法 QwQ~~
附上好久之前到现在才补对的代码 QAQ
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
const int INF = 1e9 + 7;
bool vis[110][110];
int n, m, a[110][110], min, max;
int sum, ans;
void DFS(int x, int y, int height) {
if (x < 0 || y < 0 || x > n + 1 || y > m + 1) {
return;
}
if (a[x][y] >= height) {
return;
}
if (vis[x][y]) {
return;
}
vis[x][y] = 1;
if (x > 0 && y > 0 && x <= n && y <= m) {
sum--;
}
DFS(x, y + 1, height);
DFS(x, y - 1, height);
DFS(x + 1, y, height);
DFS(x - 1, y, height);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
max = 0;
min = INF;
ans = 0;
memset(a, 0, sizeof(a));
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
min = std::min(min, a[i][j]);
max = std::max(max, a[i][j]);
}
}
for (int i = min + 1; i <= max; i++) {
memset(vis, 0, sizeof(vis));
sum = n * m;
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= m; k++) {
if (a[j][k] >= i) {
sum--;
}
}
}
DFS(0, 0, i);
ans += sum;
}
printf("%d\n", ans);
}
return 0;
}
/**/
```