LintCode 364 Trapping Rain Water II - earthma的专栏 - 博客频道 - CSDN.NET
也就是水往地处流，因此可以通过最小堆及BFS搜索来求解该题。
Given n * m non-negative integers representing an elevation map 2d where the area of each cell is 1 * 1, compute how much water it is able to trap after raining.
给出
n * m 个非负整数，代表一张X轴上每个区域为 1 * 1 的 2d 海拔图, 计算这个海拔图最多能接住多少（面积）雨水。
给出 n * m 个非负整数，代表一张X轴上每个区域为 1 * 1 的 2D 海拔图, 计算这个海拔图最多能接住多少（面积）雨水。例如，给定一个 5*4 的矩阵：
[12,13,0,12],
[13,4,13,12],
[13,8,10,12],
[12,13,12,12],
[13,13,13,13]也就是水往地处流，因此可以通过最小堆及BFS搜索来求解该题。
首先对矩阵数据建堆，
然后从堆里面选取最小元素，进行BSF遍历，如果值相等，继续往下走，如果遇到比当前值小的，或者边境，说明该水流会流出去（遇到这种情况对遍历的数据置为-1）说明往后连通该区域的水都会流出去，如果BFS一遍发现没有到边界和遇到比起小的点，则将遍历过的点的值设为遇到的最小的点，并更新水的流量，继续进行遍历。直至所有点都为-1为止，输出结果
http://www.jianshu.com/p/540ee7ec725b- 维护一个最小堆，保存最外面一圈的高度，因为最矮的格子决定了水能存放多少
- 每次取最小高度 h，与周围4个中没有被访问过的元素进行比较
- 如果该元素的高度小于 h，则注水到其中，并将其加入到最小堆中，设置该元素被访问过
- 如果该元素的高度大于 h，则直接将其加入到最小堆中，设置改元素被访问过
- 创建一个cell类，封装x, y坐标以及高度h，还有定义compare规则
- 定义一个
dx = [1, -1, 0, 0]和dy = [0, 0, 1, -1]用于生成坐标(x, y)上下左右的点
class Cell:
def __init__(self, x, y, h):
self.x, self.y, self.h = x, y, h
def __cmp__(self, other):
if self.h < other.h:
return -1
elif self.h > other.h:
return 1
else:
return 0
class Solution:
# @param heights: a matrix of integers
# @return: an integer
def __init__(self):
self.dx = [1,-1,0,0]
self.dy = [0,0,1,-1]
def trapRainWater(self, heights):
if len(heights) == 0:
return 0
q = Queue.PriorityQueue()
n = len(heights)
m = len(heights[0])
visit = [[False for i in range(m)] for i in range(n)]
for i in range(n):
q.put(Cell(i, 0, heights[i][0]))
q.put(Cell(i, m-1, heights[i][m-1]))
visit[i][0] = True
visit[i][m-1] = True
for i in range(m):
q.put(Cell(0, i, heights[0][i]))
q.put(Cell(n-1, i, heights[n-1][i]))
visit[0][i] = True
visit[n-1][i] = True
ans = 0
while not q.empty():
now = q.get()
for i in range(4):
nx = now.x + self.dx[i]
ny = now.y + self.dy[i]
if 0 <= nx and nx < n and 0 <= ny and ny < m and not visit[nx][ny]:
visit[nx][ny] = True
q.put(Cell(nx, ny, max(now.h,heights[nx][ny])))
ans += max(0, now.h - heights[nx][ny])
return ans- 用heap保存最外围的点，并且快速求得最小值
- 用一个visited matrix保存visit过的点
每次得到最外围的最小值，然后往内灌水（四个方向）
from heapq import *
class Solution:
# @param heights: a matrix of integers
# @return: an integer
def trapRainWater(self, heights):
# write your code here
if not heights:
return 0
heap = []
rowNum = len(heights)
colNum = len(heights[0])
visited = [[False for a in range(colNum)] for b in range(rowNum)]
result = 0
#add outside into heap
for i in range(rowNum):
heappush(heap, (heights[i][0], i, 0))
heappush(heap, (heights[i][colNum-1], i, colNum-1))
visited[i][0] = True
visited[i][colNum-1] = True
for j in range(1, colNum):
heappush(heap, (heights[0][j], 0, j))
heappush(heap, (heights[rowNum-1][j], rowNum-1, j))
visited[0][j] = True
visited[rowNum-1][j] = True
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
while heap:
curr = heappop(heap)
for x in range(4):
nx = curr[1] + dx[x]
ny = curr[2] + dy[x]
if nx >= 0 and nx < rowNum and ny >= 0 and ny < colNum and not visited[nx][ny]:
visited[nx][ny] = True
heappush(heap, (max(curr[0], heights[nx][ny]), nx, ny))
result += max(0, curr[0] - heights[nx][ny])
return result
从1维升级为2维，给一个matrix, 每个cell表示海报高度，求问最多能装多少水。（最外面一圈不能装水）
BFS + Heap的解法。
从最外面一圈开始，往里找。开始的时候把最外面一圈的海拔高度加入到一个minHeap，取出外面一圈海拔最低的点curr，看四周没有被visit过的点，因为是BFS并且是由内而外，所以四周没有被visit过的，只有可能是当前一层或者更内层。
如果四周其中有一个点的海报高度低于curr，说明这个点上方肯定能积水，因为curr是外层海拔最低的，其他的海拔都要比curr还高，因此不存在那种一路低下去低到另一边的情况。
如果在curr四周发现能积水的点adj，更新result的同时，把adj也offer进minHeap以便继续往内层搜索，但是加入minHeap的高度不是adj本来的高度，而是curr的高度。因为如果再往里一层还有点比adj还低，那么蓄水高度就应该是curr.height – height，而不是adj.height – height了。
下面的code记得多读甚至多写几遍，一来是因为这道题的思路不好理解，二来也该学学matrix bfs/dfs看四周时候这种比较clean的写法了，别整天写4个方向写4个递归。
public int trapWater(int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return 0; } int m = matrix.length; int n = matrix[0].length; PriorityQueue<Node> minHeap = new PriorityQueue<>(10, new Comparator<Node>() { public int compare(Node a, Node b) { return a.height - b.height; } }); boolean[][] visited = new boolean[m][n]; // left and right border for (int i = 0; i < m; i++) { Node a = new Node(i, 0, matrix[i][0]); Node b = new Node(i, n - 1, matrix[i][n - 1]); minHeap.offer(a); minHeap.offer(b); visited[i][0] = true; visited[i][n - 1] = true; } // top and bottom border for (int j = 0; j < n; j++) { Node a = new Node(0, j, matrix[0][j]); Node b = new Node(m - 1, j, matrix[m - 1][j]); minHeap.offer(a); minHeap.offer(b); visited[0][j] = true; visited[m - 1][j] = true; } int[] row = {-1, 1, 0, 0}; int[] col = {0, 0, -1, 1}; int result = 0; while (!minHeap.isEmpty()) { Node curr = minHeap.poll(); for (int i = 0; i < 4; i++) { int newX = curr.x + row[i]; int newY = curr.y + col[i]; if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) { result += Math.max(0, curr.height - matrix[newX][newY]); int newHeight = Math.max(curr.height, matrix[newX][newY]); minHeap.offer(new Node(newX, newY, newHeight)); visited[newX][newY] = true; } } } return result; }
一圈的高度中的最小值，而找到这个最小值我们可以用heap来快速得到，python的heap是用heapq这个library来实现