降水 WATER
题意描述
- 给定一个 (n*m) 的场地，每一个格子上有高度为 (h_{i,j})的长方体，现在突然下雨了，问能存多少水？
Solve
-
题目大意
- 二维的积水问题。
-
木桶原理：桶能装的水的多少取决于最短的木板。
-
同理，一块土地积存的水取决于最低的那个边界，我们知道矩阵最边上的位置是不可能存水的（h > 1嘛），就从边上向内搜索，找到更低的地方就可以存水。
-
w是每块方格最高的水位（不能存水的格子水位就等于高度）。
-
具体实现过程：
- 将边界上的点（横坐标等于1或n，纵坐标等于1或m）放入小根堆。
- 每次取出堆顶（即高度最小的点），进行BFS，这里进行BFS是因为DFS在这种可以随意走，一直递归下去（指没有进行过回溯）就可能跑完的图有爆栈的可能，其实这到题还是没什么关系，我的电脑实测可以递归到26万层左右，这道题只有1万个点。
- 进行BFS的时候，搜索到低的点就改变其最高水位，有高的点就在判断没有进入过堆后压入堆中
-
详见代码注释
Code
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 305;
struct Node {
int x, y, h;
Node() {};
Node(int a, int b, int c) {
x = a, y = b, h = c;
}
bool operator < (const Node &b) const {
return h > b.h;
}//重载运算符，这是小根堆
};
int T, n, m, h[N][N], w[N][N], ans;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};//Bfs时的4个方向
priority_queue<Node> que;//堆
queue<Node> q;//Bfs用的队列
bool vis[N][N];//标记是否入过堆
void Bfs(Node a) {
q.push(a);
while (!q.empty()) {
Node u = q.front(); q.pop();
if (w[u.x][u.y] != -1) continue;
w[u.x][u.y] = a.h;
for (int k = 0; k < 4; ++k) {
int tx = u.x + dx[k];
int ty = u.y + dy[k];
if (tx < 1 || tx > n || ty < 1 || ty > m) continue;//超出了边界
if (w[tx][ty] != -1) continue;//已经访问过且赋值
if (h[tx][ty] <= a.h) q.push(Node(tx, ty, 0));//高度低的入队，继续Bfs
else if (!vis[tx][ty]) //高度高的压入堆
que.push(Node(tx, ty, h[tx][ty])), vis[tx][ty] = 1;
}
}
}
int main() {
scanf("%d", &T);//P5930不需要多组数据
while (T--) {
ans = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
scanf("%d", &h[i][j]);
w[i][j] = -1;//初始化为-1，为未访问标记
if (i == 1 || i == n || j == 1 || j == m)//将边界入堆并标记
que.push(Node(i, j, h[i][j])), vis[i][j] = 1;
else vis[i][j] = 0;
}
while (!que.empty()) {//每次取出最低的进行操作
Node u = que.top(); que.pop();
if (w[u.x][u.y] != -1) continue;//如果已经访问那就不需要了
Bfs(u);
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
ans += w[i][j] - h[i][j];//w-h即水的深度
printf("%d
", ans);
}
return 0;
}
双倍经验