Улавливание дождевой воды ii (LeetCode) с отверстием (0)

Question

https://leetcode.com/problems/trapping-rain-water-ii/

Учитывая матрицу положительных чисел m x n, представляющую высоту каждая элементарная ячейка в 2D-карте высот, рассчитать объем воды, которую он может попасть в ловушку после дождя.

Небольшое дополнение: есть ли в нем дыра, а вся платформа в воздухе? Сколько он на самом деле может хранить?

Хотя я могу искать ограничивающую область вокруг отверстия и рассчитать, сколько воды там потрачено, я могу определить только прямоугольную ограничивающую область (Случай 1), но для второго случая, как вы можете найти и рассчитать воду в этой области :

Если я просто посмотрю на прямоугольную область, которая состоит из ограничивающей области, определенной серыми линиями, вычислите количество воды, хранящейся здесь, затем вычтите из общей суммы, вода, хранящаяся в зеленой области, будет удалена, чего не должно быть. И большая проблема, что если ее вообще не существует?

Или есть какой-то подход, который я пропускаю, любые предложения приветствуются.

Answer 1

Здесь 'подход, который работал для меня.

Я смотрел на отдельные клетки, а не на области.

Пусть a[i][j] - общая высота комбинированного камня (или любого другого материала, которыйэто) и вода над ним.

Тогда мы имеем:

a[i][j] = max(height[i][j], min(a[i+1][j], a[i][j+1], a[i-1][j], a[i][j-1]))

Часть «max» предназначена для предотвращения того, чтобы значение было меньше каменной части.А минимальная часть - убедиться, что вода удерживается соседними ячейками.

Для границ уровень воды равен нулю, поэтому a[i][j] = height[i][j].Для других ячеек мы можем начать с очень большого числа.

Чтобы проиллюстрировать это немного: предположим, вы точно знаете, что уровень воды для соседней ячейки не может быть больше 7 (например).Тогда уровень воды в вашей текущей ячейке также не может быть больше 7: буквально ничто не может удержать поток воды в направлении этой соседней ячейки.

Кстати, если у вас есть «дыра»в ячейке тогда a [i] [j] = 0, поскольку там не может накапливаться вода.

Мы можем многократно применять эту формулу как своего рода «расслабление», пока она больше не станет возможной.Когда это больше невозможно, у нас есть окончательная конфигурация, и нам просто нужно рассчитать объем воды.

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

a[i][j] = max(height[i][j], min(a[i-1][j], a[i][j-1]))

изатем снизу вверх, применяя:

a[i][j] = max(height[i][j], min(a[i+1][j], a[i][j+1]))

, повторяя его снова и снова, пока изменяется хотя бы одно значение ячейки.