求热带岛屿下雨后积水量

让我们取两个矩阵：原始的一个，让我们表示它I。而工作的，与原来的大小相同，但填充了级别的最大可能理论值（我以 10000 的边距取它），让我们表示它W。接下来，我们递归地遍历整个字段，从岛上的每个极端单元开始。递归函数将处理单元的坐标和当前水位作为输入。如果接收到的当前电平低于单元格的初始高度（我们取自I），那么我们接受当前电平等于单元格的高度。因此，我们得到了所有相邻单元格中水可以上升到的水平，如果它们的高度较低的话。在工作矩阵中，我们确定了邻居的最小级别，即 此单元格的最大可能级别。让我提醒您，最初我们将其设为 10000。因此，如果单元格的工作矩阵中的级别结果高于当前级别，那么我们将其与当前级别相等。因此，我们在通过所有邻居时将级别降低到最低限度。还有一个更重要的规则：如果当前级别大于工作矩阵中已经固定的级别，那么我们立即停止递归绕过。一旦W级别较低，这意味着我们已经从流量较低的单元格到达这个单元格，并且没有必要检查更多的邻居，我们在那里并且最大值较低。

为了加快工作速度，您可以按高度增加的顺序绕过边界单元。然后，我们将立即用最小值淹没所有可从它们访问的区域。并且在从更高的单元进行分析时，我们不会反复绕过这些区域。

perl 示例

#!/usr/bin/perl
use strict;
use warnings;

my @I;        # Исходная матрица
my @W;        # Рабочая матрица
my ($MX,$MY); # Размеры матрицы
while(<DATA>) {  # Читаем исходую матрицу
  my @row=();
  chomp;
  last if(!$_);
  push @row, $_ for split / +/;
  push @I, \@row;
  $MX=@row; $MY++;  # Запоминаем размеры
  my @row2=();      # И заполняем начальными значениями рабочую
  push @row2,10000 for(1..$MX);
  push @W, \@row2;
}
$MX--; $MY--;
# обходим все 4 стороны прямоугольника
cell(0,$_,0)   for(1..$MY);
cell($MX,$_,0) for(1..$MY);
cell($_,0,0)   for(1..$MX);
cell($_,$MY,0) for(1..$MX);

# Печать результирующей матрицы и расчет объема воды
my $summ=0;
my $y=0;
for(@W) {
  $,=" ";
  print "@$_\n";
  for my $x(0..$MX) { $summ+=$W[$y][$x]-$I[$y][$x]; }
  $y++;
}

print "RESULT = $summ\n";

# Основная рабочая, рекурсивная функция
sub cell {
  my($x, $y, $lev)=@_;
  return if($x<0 || $y<0 || $x>$MX || $y>$MY);  # Проверяем выход за пределы поля
  return if($W[$y][$x]<=$lev);    # Максимум клетки ниже или равен - мы тут были
  $lev=$I[$y][$x] if($lev < $I[$y][$x]);  # Повышаем текущий уровень, если ниже изначального для клетки
  $W[$y][$x]=$lev;    # Устанавливаем текущий максимум
  cell($x-1,$y,$lev); # И обходим всех 4х соседей рекурсивно
  cell($x+1,$y,$lev);
  cell($x,$y-1,$lev);
  cell($x,$y+1,$lev);
}

有一个基于明显限制的简单解决方案：

• 笼子里的水位不能低于笼子的高度
• 一个单元格中的水位不能大于相邻单元格中的水位

算法：

Для начала уровень воды во всех клетках можно установить равным наибольшей высоте.

Уровень воды в клетке на периметре острова равен высоте этой клетки.

До тех пор пока уровень воды не стабилизировался (пока его можно понизить):
  Для каждой клетки на острове,
    если уровень в ней не минимальный (если его можно понизить), 
      сравниваем уровень с соседями во всех направлениях (север, юг, запад, восток)
        если уровень у соседей меньше,
          то понижаем до уровня соседей (или до высоты самой клетки — что больше)

Чтобы найти общее количество удерживаемой воды, для всех клеток,
суммируем разницу между уровнем воды и высотой в этой клетке

在 Python 上：

NORTH, SOUTH, WEST, EAST = (0, -1), (0, 1), (-1, 0), (1, 0)


def max_water_heldover_bruteforce(h):
    # fill initially upto the max height
    max_height = max(max(row) for row in h)
    L = [[max_height] * len(row) for row in h]

    # water level on the perimeter is equal to the height
    L[0][:] = h[0]    # North row
    L[-1][:] = h[-1]  # South row
    for column_index in [0, -1]:  # West, East columns
        # L[:,column_index] = h[:,column_index]
        for level_row, h_row in zip(L, h):  # for each row
            level_row[column_index] = h_row[column_index]  # set level

    while True:  # until the level is stable
        changed = False
        for i in range(1, len(h) - 1):
            for j in range(1, len(h[i]) - 1):
                if L[i][j] != h[i][j]:  # if not already at the minimum
                    for dx, dy in [NORTH, SOUTH, WEST, EAST]:
                        if L[i + dy][j + dx] < L[i][j]:  # lower water level
                            L[i][j] = max(L[i + dy][j + dx], h[i][j])
                            changed = True
        if not changed:
            break

    # find how much water held over the island
    return sum((level - height)
               for row, h_row in zip(L, h)
               for level, height in zip(row, h_row))

检查问题中的示例：

inputs = [
    """
4 5 4
3 1 5
5 4 1
""",
    """
5 3 4 5
6 2 1 4
3 1 1 4
8 5 4 3
""",
    """
2 2 2
2 1 2
2 1 2
2 1 2
"""]

output = [2, 7, 0]
for input_text, expected in zip(inputs, output):
    heights = [[int(n) for n in line.split()]
               for line in input_text.splitlines() if line.strip()]
    got = max_water_heldover_bruteforce(heights)
    assert got == expected, (got, expected, heights)

基于以随机顺序（来自@Mike 的回答和）遍历岛屿的解决方案max_water_heldover_bruteforce()具有时间复杂度O(ncells * min(ncells, max_height))。它们可以O(ncells * log ncells)通过在低水位到高水位的瓷砖周围走动来升级。这允许每个单元格仅被访问一次。

O(n log n) 算法

我们将单元格放在岛边界的堆中（min-heap）。这些细胞中的水位等于它们的高度。

我们按照水位升序访问堆中的所有单元格。
对于访问单元格的每个邻居（上、下、左、右），水位等于
访问单元格中的水位（因为它是最小堆属性中的最小值）
或高度单元格本身（因为水位不能小于单元格的高度）
由于每个单元格只被访问一次，我们立即将保留的水量（单元格中的水位与其高度之间的差）添加到整体结果。

用 Python 实现

这是Jason Yuan对Trapping Rain Water II问题的稍微修改的解决方案：

from collections import namedtuple
from queue import PriorityQueue

NORTH, SOUTH, WEST, EAST = (0, -1), (0, 1), (-1, 0), (1, 0)
Cell = namedtuple('Cell', 'level x y')

def max_water_heldover_minheap(heights, display=None):
    q = PriorityQueue()
    nrows = len(heights)
    ncolumns = len(heights[0])
    seen = [[False] * ncolumns for _ in range(nrows)]

    # enqueue cells on the perimeter of the island
    for y in range(nrows):
        seen[y][0] = True
        q.put(Cell(heights[y][0], 0, y))  # WEST side
        seen[y][ncolumns - 1] = True
        q.put(Cell(heights[y][ncolumns - 1], ncolumns - 1, y))  # EAST

    for x in range(ncolumns):
        seen[0][x] = True
        q.put(Cell(heights[0][x], x, 0))  # NORTH side
        seen[nrows - 1][x] = True
        q.put(Cell(heights[nrows - 1][x], x, nrows - 1))  # SOUTH

    # visit all cells once starting with cells with a minimum water level
    total = 0
    while not q.empty():
        cell = q.get()
        for dx, dy in [NORTH, SOUTH, WEST, EAST]:
            x = cell.x + dx
            y = cell.y + dy
            if 0 <= y < nrows and 0 <= x < ncolumns and not seen[y][x]:
                seen[y][x] = True
                q.put(Cell(max(cell.level, heights[y][x]), x, y))
                total += max(0, cell.level - heights[y][x])
    return total

用法示例。

@David Eisenstat 指出，当问题简化为找到平面图的最小生成树时，可以使用线性 ( O(n)) 算法。@Richard 提到有一些方法适用于万亿细胞问题。请参阅3D 中截留雨水的最大体积。