原文地址：zhuanlan.zhihu.com/p/600680932
背景
之前一直流传着名为「二维接雨水」的算法题，我当时一拍脑袋脑补了一下难道是给一个复杂二维多边形然后问能接多少雨水？但一想不太可能，太复杂了不适合当成面试题来做。于是我又拍脑袋一想，会不会是类似 2D 像素游戏比如泰拉瑞亚一样一个一个方块组成的随机地形来接雨水？
说着我就开始着手来实现一个 2D 像素接雨水来玩玩，如下图所示一个随机生成的 2D 像素地图，雨水从顶上下下来，两边都会漏水，求最后平衡状态下能装多少雨水。
当然，在这之后我也手贱搜了一下真正的接雨水题是什么样子的……但怎么说呢……这也太无聊了叭。
leetcode.cn/problems/tr…
生成随机地图
玩接雨水之前，我们要先能够生成一个可用的像素地图，这个像素地图我们可以把他当成一个「山」。当然我们可以直接全部随机生成像素墙体，但是我们既然称他为山，并且也为了我们能稍微接多一些雨水，我们设计一个根据高度生成像素墙的概率随之变化的随机生成算法。
参考代码：
static createRandomInitialContent(width: number, height: number): InitialContent {
const remap = ([x0, x1]: [number, number], [y0, y1]: [number, number]) => {
const dx = x1 - x0;
const dy = y1 - y0;
return function (x: number) {
const px = (x - x0) / dx;
return y0 + px * dy;
};
}
const remapProbability = remap([0, height - 1], [0.2, 0.6]);
return Array.from({ length: height })
.map((_, h) => Array.from({ length: width })
.map(_ => Math.random() > remapProbability(h) ? BlockContent.EMPTY : BlockContent.WALL));
}
大雨漫灌 —— 搜索水流经历的路径
我们在有一张地图后，我们的目标是计算能接多少雨水，但是直接计算会比较有难度，所以我们先假设大水漫灌，从每一个最顶部的每一个空方块开始遍历，然后遍历所有可能有水流经过的地方。比如以一下这个例子为例：
我们要从 ①、②和③ 三个入口遍历这三个可以储水的区域，这里遍历直接用搜索算法就行。然后我们就得到如下一个所有可能储水的路径，如下图所示：
参考代码：
// 大水漫灌
water() {
const travelWaterPath = (block: Block | null) => {
if (!block || block.content !== BlockContent.EMPTY) {
return;
}
block.content = BlockContent.WATER;
this.waterBlocks.add(block);
travelWaterPath(block.left())
travelWaterPath(block.right())
travelWaterPath(block.bottom())
travelWaterPath(block.top())
}
for (const block of this.content[0]) {
travelWaterPath(block);
}
}
雨停漏水 —— 遍历缺口并漏掉缺口以上的水
我们虽然得到了所有「可能」储水的路径，但是我们知道它并不是一个稳定状态，还有很多水会从两边漏出去。那我们第二步就是找到所有边缘的漏水口，然后向上搜索去掉多余的水。因为漏水缺口往往是左右两边的方块，我们就直接从左右两边进行搜索。
然后向上搜索去除所有多余的水以后我们的到下图：
参考代码：
// 雨停漏水
leak() {
const travel = (block: Block | null) => {
if (!block || block.content !== BlockContent.WATER) {
return;
}
block.content = BlockContent.EMPTY;
this.waterBlocks.delete(block);
travel(block.left())
travel(block.right())
travel(block.top())
}
for (const row of this.content) {
travel(row[0]);
travel(row[this.width - 1]);
}
}
平衡水位 —— 从水平面搜索连通水域平衡水位
对于上面的简单例子来说，上面一步就已经结束了。但是仅仅就只有这样吗？当然不是，我们还得考虑一个特殊但是很常见的情况 —— 连通器效应。 我们看看一个非常简单的例子：
我们可以明显看到最后一张图得到的结果不符合我们的物理常识，我们期望得到的结果应该是如下图所示，所以我们最后一步要做的就是平衡水位：
首先，我们找到所有水平面，并且从低到高排序。然后从最低的水平面开始向下搜索，低于水平面的部分搜索连通水域，一旦搜索高于水平面则开始向上搜索去除所有水（跟雨停漏水一样）。不断迭代上面过程，直到所有水平面都被遍历过。
再让我们再看一个比较复杂的例子，经过两次迭代平衡以后所有水位达到平衡：
最后，我们只要简单计算一下我们有多少水还在地图上就能得到我们这个地图能接多少雨水了。
参考代码：
// 平衡水位
balance() {
const unresolvedBlocks = new Set(this.waterBlocks);
while (unresolvedBlocks.size > 0) {
const waterFace = [...unresolvedBlocks].filter(b => {
const top = b.top();
return !top || top.content === BlockContent.EMPTY
}).sort((a, b) => b.position[1] - a.position[1])[0];
const travelClimbing = (block: Block | null) => {
if (!block || block.content !== BlockContent.WATER || !unresolvedBlocks.has(block)) {
return;
}
block.content = BlockContent.EMPTY;
this.waterBlocks.delete(block);
unresolvedBlocks.delete(block);
travelClimbing(block.left());
travelClimbing(block.right());
travelClimbing(block.top());
}
const travelDiving = (block: Block | null) => {
if (!block || block.content !== BlockContent.WATER || !unresolvedBlocks.has(block)) {
return;
}
unresolvedBlocks.delete(block);
travelDiving(block.left())
travelDiving(block.right())
travelDiving(block.bottom())
if (block.position[1] === waterFace.position[1]) {
travelClimbing(block.top());
} else {
travelDiving(block.top());
}
}
travelDiving(waterFace);
}
}
写在最后
至此，我们如何 2D 像素接雨水就已经实现完成了。在实现的过程中我们还考虑了一些比较有趣的东西，比如考虑空气气压，某些区域雨水是不可达的。但是由于平衡气压的运算过于复杂，最后就把气压这个因素去除掉了。如果有同学知道什么比较好的方法可以教教我。
参考代码
注：TypeScript 代码，可以用 ts-node 运行。
const colors = {
bgWhite: (str: string) => `\u001b[47m${str}\u001b[49m`, bgBlue: (str: string) => `\u001b[44m${str}\u001b[49m`, blue: (str: string) => `\u001b[34m${str}\u001b[39m`, white: (str: string) => `\u001b[37m${str}\u001b[39m`,}enum BlockContent { EMPTY = 0, WALL = 1, WATER = 2,};type Position = readonly [number, number];
class Block {
content: BlockContent;
readonly hill: Hill;
readonly position: Position;
constructor(hill: Hill, position: Position) {
this.content = BlockContent.EMPTY;
this.hill = hill;
this.position = position;
}
left(): Block | null { return this.hill.getBlock([this.position[0] - 1, this.position[1]]) }
right(): Block | null { return this.hill.getBlock([this.position[0] + 1, this.position[1]]) }
top(): Block | null { return this.hill.getBlock([this.position[0], this.position[1] - 1]) }
bottom(): Block | null { return this.hill.getBlock([this.position[0], this.position[1] + 1]) }
show(): string {
return ({
[BlockContent.EMPTY]: ' ',
[BlockContent.WALL]: colors.bgWhite(' '),
[BlockContent.WATER]:
!this.top() || [BlockContent.EMPTY].includes(this.top()?.content as BlockContent)
? colors.bgBlue('^^')
: colors.bgBlue(' '),
})[this.content];
}
}
type InitialContent = BlockContent[][];
class Hill {
readonly waterBlocks: Set<Block> = new Set;
readonly width: number;
readonly height: number;
readonly content: ReadonlyArray<ReadonlyArray<Block>>;
constructor(width: number, height: number, initialContent?: InitialContent) {
this.width = width;
this.height = height;
this.content = (initialContent || Hill.createRandomInitialContent(width, height))
.map((row, y) => row.map((c, x) => {
const block: Block = new Block(this, [x, y]);
block.content = c;
return block;
}));
}
getBlock([x, y]: Position) {
return this.content[y]?.[x];
}
show() {
for (const row of this.content) {
console.log('|' + row.map(b => b.show()).join('') + '|')
}
console.log(colors.bgWhite(''.padEnd(this.width * 2 + 2, ' ')))
console.log('water: ', this.waterBlocks.size)
}
showSaveData() {
console.log('[')
console.log(this.content.map(row => ` [${row.map(b => b.content === BlockContent.WALL ? BlockContent.WALL : BlockContent.EMPTY).join(',')}]`).join(',\n'));
console.log(']')
}
// 大水漫灌
water() {
const travelWaterPath = (block: Block | null) => {
if (!block || block.content !== BlockContent.EMPTY) {
return;
}
block.content = BlockContent.WATER;
this.waterBlocks.add(block);
travelWaterPath(block.left())
travelWaterPath(block.right())
travelWaterPath(block.bottom())
travelWaterPath(block.top())
}
for (const block of this.content[0]) {
travelWaterPath(block);
}
}
// 雨停漏水
leak() {
const travel = (block: Block | null) => {
if (!block || block.content !== BlockContent.WATER) {
return;
}
block.content = BlockContent.EMPTY;
this.waterBlocks.delete(block);
travel(block.left())
travel(block.right())
travel(block.top())
}
for (const row of this.content) {
travel(row[0]);
travel(row[this.width - 1]);
}
}
// 平衡水位
balance() {
const unresolvedBlocks = new Set(this.waterBlocks);
while (unresolvedBlocks.size > 0) {
const waterFace = [...unresolvedBlocks].filter(b => {
const top = b.top();
return !top || top.content === BlockContent.EMPTY
}).sort((a, b) => b.position[1] - a.position[1])[0];
const travelClimbing = (block: Block | null) => {
if (!block || block.content !== BlockContent.WATER || !unresolvedBlocks.has(block)) {
return;
}
block.content = BlockContent.EMPTY;
this.waterBlocks.delete(block);
unresolvedBlocks.delete(block);
travelClimbing(block.left());
travelClimbing(block.right());
travelClimbing(block.top());
}
const travelDiving = (block: Block | null) => {
if (!block || block.content !== BlockContent.WATER || !unresolvedBlocks.has(block)) {
return;
}
unresolvedBlocks.delete(block);
travelDiving(block.left())
travelDiving(block.right())
travelDiving(block.bottom())
if (block.position[1] === waterFace.position[1]) {
travelClimbing(block.top());
} else {
travelDiving(block.top());
}
}
travelDiving(waterFace);
}
}
collectRain() {
this.show();
console.log('=== water ===')
this.water();
this.show();
console.log('=== leak ===')
this.leak();
this.show();
console.log('=== balance ===')
this.balance();
this.show();
console.log('=== save date ===')
this.showSaveData();
}
static createRandomInitialContent(width: number, height: number): InitialContent {
const remap = ([x0, x1]: [number, number], [y0, y1]: [number, number]) => {
const dx = x1 - x0;
const dy = y1 - y0;
return function (x: number) {
const px = (x - x0) / dx;
return y0 + px * dy;
};
}
const remapProbability = remap([0, height - 1], [0.2, 0.6]);
return Array.from({ length: height })
.map((_, h) => Array.from({ length: width })
.map(_ => Math.random() > remapProbability(h) ? BlockContent.EMPTY : BlockContent.WALL));
}
}
const hill = new Hill(20, 10);
hill.collectRain();
一些测试用例：
// cases
export const cases = [
[
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0],
[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0],
[0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1],
[1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1],
[0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1],
[0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1],
[0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1]
],
[
[0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1],
[0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1],
[0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1]
],
[
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0],
[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1],
[1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1],
[1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1],
[0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1],
[0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
],
[
[0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0],
[1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1],
[0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1],
[1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1],
[0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0],
[1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1]
],
[
[0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0],
[0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0],
[1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1],
[1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1],
[1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0],
[1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1]
],
[
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
[1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0],
[1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0],
[1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0]
],
[
[0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0],
[1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0],
[1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1],
[1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1],
[0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0],
[0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1]
],
[
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1],
[0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0],
[0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0],
[1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0]
],
[
[0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1],
[0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1],
[1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1],
[1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0]
]
];