Улавливание дождевой воды в матрице

Опубликовано: 22 Сентября, 2022

Дана матрица arr[][] размерности M*N , состоящая из положительных целых чисел, где arr[i][j] представляет собой высоту каждой элементарной ячейки, задача состоит в том, чтобы найти общий объем воды, попавшей в матрицу после дождя. .

Примеры:

Input: arr[][] = {{4, 2, 7}, {2, 1, 10}, {5, 10, 2}} 
Output: 1
Explanation:
The rain water can be trapped in the following way:

  1. The cells, {(0, 0), (0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), (2, 2)} traps 0 unit volume of rain water as all water goes out of the matrix as cells are on the boundary.
  2. The cell (2, 2) traps 1 unit volume of rain water in between the cells {(0, 1), (1, 0), (1, 2), and (2, 1)}.

Therefore, a total of 1 unit volume of rain water has been trapped inside the matrix.

Input: arr[][] = {{1, 4, 3, 1, 3, 2}, {3, 2, 1, 3, 2, 4}, {2, 3, 3, 2, 3, 1}}
Output: 4

Подход: Данная проблема может быть решена с использованием жадной техники и Min-Heap. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте Min-Heap, используя priority_queue, скажем, PQ , для хранения пар позиций ячейки и ее высоты.
  • Переместите все граничные ячейки в PQ и пометьте все перемещенные ячейки как посещенные.
  • Инициализируйте две переменные, скажем, ans как 0 и maxHeight как 0 , чтобы сохранить общий объем и максимальную высоту всех ячеек в PQ соответственно.
  • Повторяйте до тех пор, пока PQ не станет пустым, и выполните следующие шаги:
    • Сохраните верхний узел PQ в переменной, скажем, front , и сотрите верхний элемент PQ .
    • Обновите значение maxHeight как максимальное значение maxHeight и front.height .
    • Теперь перейдите ко всем соседним узлам текущей ячейки (front.X, front.Y) и сделайте следующее:
      • Если соседняя ячейка действительна, т. е. ячейка не вышла за границы и еще не посещена, то вставьте значение соседней ячейки в PQ.
      • Если высота соседней ячейки меньше, чем maxHeight , увеличьте ответ на разницу maxHeight и высоты соседней ячейки.
  • Наконец, после выполнения вышеуказанных шагов выведите значение ans как результирующую воду, оставшуюся после дождя.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: (N * M * log (N * M))
Вспомогательное пространство: O(N * M)

РЕКОМЕНДУЕМЫЕ СТАТЬИ