407. Trapping Rain Water II
Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
Note:
Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.
Example:
Given the following 3x6 height map:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]
Return 4.
The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.
After the rain, water is trapped between the blocks. The total volume of water trapped is 4.
Solution
If height has length 0, then return 0.
Use priority queue and breadth first search. For each cell, store its row, column and height.
To calculate the amount of water trapped in a terrain, start by adding all the cells on the border of the terrain to a priority queue. Each cell’s height is compared, and the cell with the smallest height is polled first.
After a cell is polled from the queue, its adjacent cells are considered. If an adjacent cell has a lower height, then water is trapped in that cell. Calculate the amount of water trapped by taking the difference in height between the two cells, add that amount to the result, and offer the adjacent cell to the priority queue with the height of the current cell.
If an adjacent cell has a greater height, then that cell will not have any trapped water. Simply offer the adjacent cell to the priority queue using its own height.
Finally, return the total amount of trapped water.
JAVA
import java.util.PriorityQueue; class Solution { public int trapRainWater(int[][] heightMap) { if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) return 0; int rows = heightMap.length, columns = heightMap[0].length; boolean[][] visited = new boolean[rows][columns]; PriorityQueue<Cell> priorityQueue = new PriorityQueue<>(); // Top/bottom border process for (int i = 0; i < columns; i++) { visited[0][i] = true; visited[rows - 1][i] = true; priorityQueue.offer(new Cell(0, i, heightMap[0][i])); priorityQueue.offer(new Cell(rows - 1, i, heightMap[rows - 1][i])); } // Left/right border process for (int i = 1; i < rows - 1; i++) { visited[i][0] = true; visited[i][columns - 1] = true; priorityQueue.offer(new Cell(i, 0, heightMap[i][0])); priorityQueue.offer(new Cell(i, columns - 1, heightMap[i][columns - 1])); } int amount = 0; int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; while (!priorityQueue.isEmpty()) { Cell cell = priorityQueue.poll(); // Extract the cell with the lowest height int row = cell.row, column = cell.column, height = cell.height; for (int[] direction : directions) { int newRow = row + direction[0], newColumn = column + direction[1]; if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns) { if (!visited[newRow][newColumn]) { visited[newRow][newColumn] = true; int newCellHeight = heightMap[newRow][newColumn]; if (height > newCellHeight) { amount += height - newCellHeight; priorityQueue.offer(new Cell(newRow, newColumn, height)); } else { priorityQueue.offer(new Cell(newRow, newColumn, newCellHeight)); } } } } } return amount; } } class Cell implements Comparable<Cell> { int row; int column; int height; public Cell(int row, int column, int height) { this.row = row; this.column = column; this.height = height; } @Override public int compareTo(Cell other) { return this.height - other.height; } }
C++
class Solution {
typedef array<int, 3> Point;
public:
int trapRainWater(vector<vector<int>>& A) {
int M = A.size(), N = A[0].size(), dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }, ans = 0, maxH = INT_MIN;
priority_queue<Point, vector<Point>, greater<>> pq;
vector<vector<bool>> seen(M, vector<bool>(N));
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) {
pq.push({ A[i][j], i, j });
seen[i][j] = true;
}
}
}
while (pq.size()) {
auto [h, x, y] = pq.top();
pq.pop();
maxH = max(maxH, h);
for (auto &[dx, dy] : dirs) {
int a = x + dx, b = y + dy;
if (a < 0 || a >= M || b < 0 || b >= N || seen[a][b]) continue;
seen[a][b] = true;
if (A[a][b] < maxH) ans += maxH - A[a][b];
pq.push({ A[a][b], a, b });
}
}
return ans;
}
};PYTHON
import heapq class Solution: def trapRainWater(self, heightMap): if not heightMap or not heightMap[0]: return 0 rows, columns = len(heightMap), len(heightMap[0]) visited = [[False] * columns for _ in range(rows)] priority_queue = [] # Add border cells to the priority queue for i in range(columns): heapq.heappush(priority_queue, (heightMap[0][i], 0, i)) visited[0][i] = True heapq.heappush(priority_queue, (heightMap[rows - 1][i], rows - 1, i)) visited[rows - 1][i] = True for i in range(1, rows - 1): heapq.heappush(priority_queue, (heightMap[i][0], i, 0)) visited[i][0] = True heapq.heappush(priority_queue, (heightMap[i][columns - 1], i, columns - 1)) visited[i][columns - 1] = True amount = 0 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] while priority_queue: height, row, col = heapq.heappop(priority_queue) for dr, dc in directions: new_row, new_col = row + dr, col + dc if 0 <= new_row < rows and 0 <= new_col < columns and not visited[new_row][new_col]: visited[new_row][new_col] = True new_cell_height = heightMap[new_row][new_col] if height > new_cell_height: amount += height - new_cell_height heapq.heappush(priority_queue, (height, new_row, new_col)) else: heapq.heappush(priority_queue, (new_cell_height, new_row, new_col)) return amount
Comments
Post a Comment