Algorithm

每日一题-Trap_Water

[每日一题] (Trapping Rain Water II)
Trapping Rain Water II
Given n x m non-negative integers representing an elevation map 2d where the area of each cell is 1 x 1, compute how much water it is able to trap after raining.
Example
Given 5*4 matrix

[12,13,0,12]
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]
return 14.

解题思路


使用最小堆
1.对矩形的四周建堆
2.对于堆中每一元素，查探其四邻域中未查探的位置
3.如果h小于当前值，则更新水池容量，并将该位置加入堆中
4.如果h大于等于当前值，则直接加入堆中
最小堆中每次取的元素为当前水池中最短边的长度，如果每次寻找时发现了比最短边低的位置，则可以将水导入（更新水池容量），否则直接将该位置加入到水池中形成新的边缘

笔记

  最小堆的题目的特征(不断找最小)，对Python中的最小堆的使用

Python:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#!/usr/bin/env 
# -*- coding:utf-8 -*-
import heapq
M = [[12, 13, 0, 12], [13, 4, 13, 12], [13, 8, 10, 12], [12, 13, 12, 12], [13, 13, 13, 13]]
class Solution(object):
    def trapWater(self, M):
        heap = []
        heapq.heapify(heap)
        d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        n = len(M)
        m = len(M[0])
        visit = [[0 for i in xrange(m)] for I in xrange(n)]
        res = 0
        for i in xrange(n):
            for I in xrange(m):
                if i == 0 or I == 0 or i == n-1 or I == m-1:
                    heapq.heappush(heap, (M[i][I], i, I))
                    visit[i][I] = 1
        while heap != []:
            this = heapq.heappop(heap)
            for i in xrange(4):
                h = this[0]
                nr = this[1] + d[i][0]
                nl = this[2] + d[i][1]
                if nr < 0 or nl < 0 or nr >= n or nl >= m:
                    continue
                if visit[nr][nl] == 1:
                    continue
                visit[nr][nl] = 1
                tmp = M[nr][nl]
                if tmp < h:
                    res += h - tmp
                    tmp = h
                heapq.heappush(heap, (tmp, nr, nl))
        return res