Найти объём скопившейся после дождя воды на тропическом острове

#алгоритм

Текст задачи:

Предположим, в один прекрасный день вы оказались на острове прямоугольный формы.

Ландшафт этого острова можно описать с помощью целочисленной матрицы размером MxN,
каждый элемент которой задаёт высоту соответствующей области острова над уровнем моря.

К примеру, вот небольшой остров размером 3x3:

4 5 4
3 1 5
5 4 1


В сезон дождей остров полностью заливает водой и в низинах скапливается вода. Низиной
будем считать такую область острова, клетки которой граничат с клетками, большими по
высоте. При этом диагональные соседи не учитываются, а уровень моря принимается за
0. В приведённом выше примере на острове есть только одна низина — это клетка со значением
1 в середине острова (она граничит с клетками высотой 3, 5, 5 и 4).

Таким образом, после дождя высота клеток острова изменится и станет следующей:

4 5 4
3 3 5
5 4 1


Мы видим что в данном примере высота низины изменилась с 1 до 3, после чего вода
начала переливаться на соседние клетки, а затем — в море. Общий объём воды, скопившейся
на острове — 2 кубические клетки.

Вот пример посложнее:

5 3 4 5
6 2 1 4
3 1 1 4
8 5 4 3


После дождя карта острова принимает следующую форму:

5 3 4 5
6 3 3 4
3 3 3 4
8 5 4 3


Общий объём скопившейся после дождя воды на таком острове составляет целых 7 кубических
клеток!

Ваша программа должна быть по одному из шаблонов ниже.

На вход функции подается массив массивов, на выходе ожиается int - значения общего
объёма воды, скапливающейся на острове после сезона дождей для каждого из входных примеров
Ограничения:
Размер острова N и M — целые числа в диапазоне [1, 50]
Высоты на острове могут принимать значения из диапазона [1, 1000].
Вот примеры входных данных:

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


Для приведённых выше данных, результат функции программы должен быть следующим:

2

7

0

    

Ответы

Ответ 1

Возьмем две матрицы: исходную, обозначим ее I. И рабочую, такого же размера как исходная,
но заполненную максимально возможным теоретическим значением уровня (я взял с запасом
10000), обозначим ее W. Далее обходим рекурсивно все поле, последовательно начиная
с каждой крайней клетки острова. Рекурсивная функция на вход принимает координаты обрабатываемой
клетки и текущий уровень воды. Если полученный текущий уровень ниже, чем изначальная
высота клетки (берем из I) то принимаем текущий уровень равным высоте клетки. Таким
образом мы получаем тот уровень, до которого может подняться вода у всех соседних клеток,
если их высота ниже. В рабочей же матрице мы фиксируем минимальный уровень соседей,
т.е. максимально возможный уровень для данной клетки. Напомню, изначально мы его приняли
за 10000. Так вот, если уровень в рабочей матрице для клетки оказался выше, чем текущий
уровень то принимаем его равным текущему. Таким образом мы понижаем уровень до минимально
возможного при проходе через всех соседей. И еще одно важное правило: если текущий
уровень оказался больше, чем уже зафиксированный в рабочей матрице то рекурсивный обход
тут же прекращаем. Раз в W уровень ниже, значит мы уже приходили на эту клетку с клеток
с более низким стоком и проверять дальше соседей уже нет смысла, мы там были и там
максимум ниже.

Для ускорения работы можно обходить граничные клетки в порядке увеличения высоты.
Тогда мы сходу зальем минимумами все доступные от них области. И при анализе от более
высоких клеток повторно обходить эти области не будем.

Пример на perl

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

my @I;        # Исходная матрица
my @W;        # Рабочая матрица
my ($MX,$MY); # Размеры матрицы
while() {  # Читаем исходую матрицу
  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);
}


Ответ 2

Есть простое в лоб решение, основанное на очевидных ограничениях:


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


Алгоритм:

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

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

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

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


На Питоне:



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)


Ответ 3

Решения, основанные на обходе острова в произвольном порядке (из @Mike ответа и max_water_heldover_bruteforce()),
имеют временну́ю сложность O(ncells * min(ncells, max_height)). Их можно улучшить до
O(ncells * log ncells), обходя клетки, от малого уровня воды к бо́льшему. Это позволяет
посещать каждую клетку только однажды.

O(n log n) алгоритм

Помещаем клетки на границе острова в кучу (min-heap). Уровень воды в этих клетках
равен их высоте.

Посещаем все клетки из кучи в порядке возрастания уровня воды в них.
Для каждого из соседей посещаемой клетки (сверху, снизу, слева, справа) уровень воды
равен
либо уровню в посещаемой клетке (так как он наименьший по свойству min-heap)
либо высоте самой клетки (так как уровень воды не может быть меньше высоты клетки)
Так как каждая клетка посещается только раз, то сразу добавляем объём удерживаемой
воды (разница между уровнем воды в клетке и её высотой) в общий результат.

Реализация на Питоне

Вот слегка изменённое решение от 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 упоминает
что есть методы, которые применимы к задачам с триллионом клеток. См. The Maximum Volume
of Trapped Rain Water in 3D.