## 题目描述：

LeetCode 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 are trapped between the blocks. The total volume of water trapped is 4.

## 题目大意：

m和n值均小于110.每一个单元的高度在(0, 20000)之间。

BFS（广度优先搜索）

## Python代码：

``````class Solution(object):
def trapRainWater(self, heightMap):
"""
:type heightMap: List[List[int]]
:rtype: int
"""
m = len(heightMap)
n = len(heightMap[0]) if m else 0

peakMap = [[0x7FFFFFFF] * n for _ in range(m)]

q = []

for x in range(m):
for y in range(n):
if x in (0, m - 1) or y in (0, n - 1):
peakMap[x][y] = heightMap[x][y]
q.append((x, y))

while q:
x, y = q.pop(0)
for dx, dy in zip((1, 0, -1, 0), (0, 1, 0, -1)):
nx, ny = x + dx, y + dy
if nx <= 0 or nx >= m - 1 or ny <= 0 or ny >= n - 1: continue
limit = max(peakMap[x][y], heightMap[nx][ny])
if peakMap[nx][ny] > limit:
peakMap[nx][ny] = limit
q.append((nx, ny))

return sum(peakMap[x][y] - heightMap[x][y] for x in range(m) for y in range(n))
``````

```1. 单元格的高度严格小于其上、下、左、右方向的4个单元格高度

2. 单元格的高度小于或等于其上、下、左、右方向的4个单元格高度```

```首先，计算heightMap的和，记为sum0

记队头为h

使用BFS寻找一个点集vs，其中的点与h等高，并且与h直接或者间接相邻。从而得到vs的最小临近点高度，记为minh。

将vs中的所有点从队列移除；如果minh > h，则将vs中所有点的高度更新为minh，并将h加入队尾；

## Java代码：

``````import java.awt.Point;

public class Solution {

private int m, n;
private int[][] heightMap;
private int dx[] = {1, 0, -1, 0};
private int dy[] = {0, 1, 0, -1};

public int trapRainWater(int[][] heightMap) {
this.heightMap = heightMap;
this.m = heightMap.length;
if (this.m > 0) this.n = heightMap[0].length;

int sum = calcHeightMapSum();

for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (minNeighborHeight(i, j) >= heightMap[i][j]) {
}
}
}

while (!queue.isEmpty()) {
Point h = queue.iterator().next();
HashSet<Point> vs = new HashSet<Point>();
int minh = bfs(h, vs);
if (minh > heightMap[h.x][h.y]) {
for (Point e : vs) {
heightMap[e.x][e.y] = minh;
queue.remove(e);
}
} else {
for (Point e : vs) {
queue.remove(e);
}
}
}

return calcHeightMapSum() - sum;
}

private int bfs(Point p, HashSet<Point> vs) {
int ans = Integer.MAX_VALUE;
int height = heightMap[p.x][p.y];

while (!queue.isEmpty()) {
Point h = queue.removeFirst();
if (h.x == 0 || h.y == 0 || h.x == m - 1 || h.y == n - 1) {
ans = Math.min(heightMap[h.x][h.y], ans);
continue;
}
int minh = minNeighborHeight(h.x, h.y);
if (minh != height) {
ans = Math.min(minh, ans);
continue;
}
for (int k = 0; k < dx.length; k++) {
Point np = new Point(h.x + dx[k], h.y + dy[k]);
if (heightMap[np.x][np.y] != height) {
ans = Math.min(ans, heightMap[np.x][np.y]);
} else if (!vs.contains(np)) {
}
}
}
return ans;
}

private int minNeighborHeight(int i, int j) {
int minh = Integer.MAX_VALUE;
for (int k = 0; k < dx.length; k++) {
int di = i + dx[k];
int dj = j + dy[k];
minh = Math.min(minh, heightMap[di][dj]);
}
return minh;
}

public int calcHeightMapSum() {
int sum = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sum += heightMap[i][j];
}
}
return sum;
}

}
``````

Pingbacks已关闭。