Улавливание дождевой воды II

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

Пример:

Ввод: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Результат: 4
Пояснение: После дождя вода задерживается между блоками.
У нас есть два небольших пруда 1 и 3, застрявших в ловушке.
Общий объем захваченной воды равен 4.

Давайте сначала посмотрим на решение, а затем его объяснение:

import java.util.PriorityQueue;

class Cell implements Comparable<Cell> {
    int x, y, height;
    
    public Cell(int x, int y, int height) {
        this.x = x;
        this.y = y;
        this.height = height;
    }
    
    @Override
    public int compareTo(Cell other) {
        return this.height - other.height;
    }
}

public class TrappingRainWaterII {
    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) {
            return 0;
        }
        
        int m = heightMap.length;
        int n = heightMap[0].length;
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<Cell> minHeap = new PriorityQueue<>();
        
        // Add the border cells to the minHeap and mark them as visited
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    minHeap.offer(new Cell(i, j, heightMap[i][j]));
                    visited[i][j] = true;
                }
            }
        }
        
        int result = 0;
        int maxHeight = Integer.MIN_VALUE;
        
        while (!minHeap.isEmpty()) {
            Cell cell = minHeap.poll();
            maxHeight = Math.max(maxHeight, cell.height);
            
            for (int[] dir : directions) {
                int newRow = cell.x + dir[0];
                int newCol = cell.y + dir[1];
                
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
                    visited[newRow][newCol] = true;
                    int newHeight = heightMap[newRow][newCol];
                    
                    if (newHeight < maxHeight) {
                        result += maxHeight - newHeight;
                    }
                    
                    minHeap.offer(new Cell(newRow, newCol, newHeight));
                }
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        TrappingRainWaterII solution = new TrappingRainWaterII();
        int[][] heightMap = {{1, 4, 3, 1, 3, 2},
                             {3, 2, 1, 3, 2, 4},
                             {2, 3, 3, 2, 3, 1}};
        int trappedWater = solution.trapRainWater(heightMap);
        System.out.println("Trapped Water: " + trappedWater);
    }
}

Этот код определяет класс Cell для хранения координат и высоты ячеек на карте высот. Он использует очередь приоритетов (minHeap) для обработки ячеек в порядке возрастания высоты. Основная логика состоит в том, чтобы начать с пограничных ячеек и двигаться внутрь, вычисляя захваченную воду на каждом этапе.

Обратите внимание, что это решение предполагает, что входная карта высот правильно сформирована, то есть имеет как минимум три стороны ненулевой длины. При необходимости вам следует добавить проверку ввода.

Давайте шаг за шагом разберем данное Java-решение проблемы «Захват дождевой воды II»:

Создайте класс Cell:

class Cell implements Comparable<Cell> {
    int x, y, height;
    
    public Cell(int x, int y, int height) {
        this.x = x;
        this.y = y;
        this.height = height;
    }
    
    @Override
    public int compareTo(Cell other) {
        return this.height - other.height;
    }
}

Мы создаем класс Cell для представления ячейки на карте высот.
Каждая ячейка имеет три атрибута: x и y, представляющие ее координаты, и height, представляющие ее высоту.
Мы реализуем интерфейс Comparable для сравнения ячеек по их высоте.

2. Инициализируйте переменные и структуры данных:

    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) {
            return 0;
        }
        
        int m = heightMap.length;
        int n = heightMap[0].length;
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<Cell> minHeap = new PriorityQueue<>();

Метод trapRainWater принимает на вход двумерный массив heightMap, который представляет карту высот.
Мы проверяем, является ли вход пустым или нулевым, и возвращаем 0, если это так.
m и n обозначают размеры карты высот.
directions — это двумерный массив, определяющий четыре возможных направления перемещения (вниз, вверх, вправо и влево).
visited — это логический массив, который отслеживает, какие ячейки были посещены.
minHeap — приоритетная очередь из Cell объектов, которая будет использоваться для обработки ячеек в порядке возрастания высоты.

4. Добавьте ячейки границ к minHeap и отметьте их как посещенные:

        // Add the border cells to the minHeap and mark them as visited
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    minHeap.offer(new Cell(i, j, heightMap[i][j]));
                    visited[i][j] = true;
                }
            }
        }

На этом этапе мы перебираем все ячейки карты высот.
Если ячейка находится на границе (т. е. ее индекс строки или столбца равен 0, или m-1, или 0, или n-1), мы добавляем ее к minHeap с ее координатами и высотой.
Также отмечаем ячейку как посещенную.

5. Инициализируем переменные для результата и максимальной высоты:

        int result = 0;
        int maxHeight = Integer.MIN_VALUE;

result будет хранить всю захваченную воду.
maxHeight отслеживает максимальную высоту, обнаруженную во время обработки.

6. Обработка ячеек из minHeap:

        while (!minHeap.isEmpty()) {
            Cell cell = minHeap.poll();
            maxHeight = Math.max(maxHeight, cell.height);

Мы входим в цикл, который продолжается до тех пор, пока minHeap не станет пустым.
Мы извлекаем ячейку минимальной высоты из minHeap и обновляем maxHeight при необходимости.

7. Исследуйте соседние ячейки и посчитайте захваченную воду:

            for (int[] dir : directions) {
                int newRow = cell.x + dir[0];
                int newCol = cell.y + dir[1];
                
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
                    visited[newRow][newCol] = true;
                    int newHeight = heightMap[newRow][newCol];
                    
                    if (newHeight < maxHeight) {
                        result += maxHeight - newHeight;
                    }
                    
                    minHeap.offer(new Cell(newRow, newCol, newHeight));
                }
            }
        }

Для каждого направления (вверх, вниз, влево, вправо) вычисляем координаты соседней ячейки (newRow и newCol).
Проверяем, находится ли соседняя ячейка в границах карты высот и не была ли она посещена.
Если высота соседней ячейки меньше maxHeight, в ней может задерживаться вода. Мы вычисляем захваченную воду как разницу между maxHeight и высотой соседней ячейки и добавляем ее к result.
Соседнюю ячейку отмечаем как посещенную и добавляем ее в minHeap для дальнейшего исследования.

8. Верните всю захваченную воду.

Таким образом, это решение использует приоритетную очередь для обработки ячеек в порядке возрастания высоты, моделируя улавливание дождевой воды и рассчитывая общее количество захваченной воды. Алгоритм начинается с граничных ячеек и движется внутрь, отслеживая максимальную встреченную высоту. Он эффективно обрабатывает карту высот, чтобы найти застрявшую воду.

Улавливание дождевой воды II — Жесткий

Вопросы по теме