自动搬运

查看原文

来自洛谷，原作者为

	STA_Morlin 命运可以被相信，但不能被期待。

搬运于2025-08-24 22:15:43，当前版本为作者最后更新于2022-07-27 22:02:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P5930 降水 の 题目传送门。

题目简化

给定一块区域 $a_{n, m}$，每块土地都有一个高度。
下雨了。

求其共装了多少水。

思路讲解

稍微观察，可以发现，只有本身与外界隔离时，才会积住水。
那么是不是可以从外界向里看？
自然，最外面一圈是积不住水的，所以从最外圈开始向内泄水。
考虑搜索。

代码实现

考虑 dfs 或 bfs。

dfs

在看到这题的第一眼，我就想写 dfs，为什么？简单啊。
先将四周存入一个数组 $r$，再挨个 dfs。

CODE

void dfs (clod t) {
	for (int i = -1; i <= 1; ++ i) for (int j = -1; j <= 1; ++ j) {
		int px = t.x+i, py = t.y+j;
		if (abs(i+j)==1 && px>1 && py>1 && px<n && py<m && w[px][py] > w[t.x][t.y]) {
			if(w[t.x][t.y] > h[px][py]) w[px][py] = w[t.x][t.y];
			if(w[t.x][t.y] <= h[px][py]) w[px][py] = h[px][py];
			v[px][py] = 1;
			dfs({px, py, w[px][py]});
		}
	}
	return ;
}

弄出来后，感觉太慢了，$n$ 和 $m$ 如果再大一点就寄了，我们要有危机意识，所以考虑优化：加入 $v_{n, m}$，判断是否遍历过。
弄完之后发现：每块土不一定只从一个方向泄水，于是寄了。

怎么办呢？我们还是得有危机意识，考虑 bfs。

dfs

还是先将四周存入队列 $q$，再进行 bfs。

CODE

void bfs () {
	while (!q.empty()) {
		clod t = q.top();
		q.pop();
		for (int i = -1; i <= 1; ++ i) for (int j = -1; j <= 1; ++ j) {
			int px = t.x+i, py = t.y+j;
			if (abs(i+j)==1 && px>1 && py>1 && px<n && py<m && w[px][py] > w[t.x][t.y]) {
				if(w[t.x][t.y] > h[px][py]) w[px][py] = w[t.x][t.y];
				if(w[t.x][t.y] <= h[px][py]) w[px][py] = h[px][py];
				q.push({px, py, w[px][py]});
			}
		}
	}
	return ;
}
int main () {

	...
}

啊！神清气爽！虽然还是被最优解碾压，但也才0.1s，稳过了就。

E.N.D.