Задача: 407. Trapping Rain Water II
Сложность: hard

Задав целочисленную матрицу heightMap размером m x n, представляющую высоту каждой ячейки на двумерной карте рельефа, верните объем воды, который она может задержать после дождя.

Пример:

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4

👨‍💻 Алгоритм:

1⃣Используйте приоритетную очередь для хранения всех ячеек по периметру матрицы.

2⃣Постепенно извлекайте ячейки из очереди, рассматривая их соседей. Если соседняя ячейка ниже текущей, добавьте разницу в высоте к общему объему воды и обновите её высоту.

3⃣Повторите процесс, пока все ячейки не будут обработаны.

😎 Решение:

function trapRainWater($heightMap) {
    $m = count($heightMap);
    $n = count($heightMap[0]);
    if ($m <= 2 || $n <= 2) return 0;
    $visited = array_fill(0, $m, array_fill(0, $n, false));
    $heap = new SplPriorityQueue();
    for ($i = 0; $i < $m; $i++) {
        for ($j of [0, $n-1]) {
            $heap->insert([$heightMap[$i][$j], $i, $j], -$heightMap[$i][$j]);
            $visited[$i][$j] = true;
        }
    }
    for ($j = 0; $j < $n; $j++) {
        for ($i of [0, $m-1]) {
            $heap->insert([$heightMap[$i][$j], $i, $j], -$heightMap[$i][$j]);
            $visited[$i][$j] = true;
        }
    }
    $directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    $water = 0;
    while (!$heap->isEmpty()) {
        list($height, $x, $y) = $heap->extract();
        foreach ($directions as $direction) {
            $nx = $x + $direction[0];
            $ny = $y + $direction[1];
            if ($nx >= 0 && $nx < $m && $ny >= 0 && $ny < $n && !$visited[$nx][$ny]) {
                $visited[$nx][$ny] = true;
                $water += max(0, $height - $heightMap[$nx][$ny]);
                $heap->insert([max($height, $heightMap[$nx][$ny]), $nx, $ny], -max($height, $heightMap[$nx][$ny]));
            }
        }
    }
    return $water;
}

Ставь 👍 и забирай 📚 Базу знаний