407.雨水を閉じ込めるII

407 Trapping Rain Water Ii

与えられたm x n 2D標高マップの各ユニットセルの高さを表す正の整数の行列を使用して、雨が降った後にトラップできる水の量を計算します。

注意：
両方とも m そして n 各ユニットセルの高さは0より大きく、20,000未満です。

例：

上の画像は標高マップを表していますimport heapq class Solution: def trapRainWater(self, a): ''' :type heightMap: List[List[int]] :rtype: int ''' if not a or not a[0]: return 0 n,m=len(a),len(a[0]) if n<=2 or m<=2: return 0 q = [] d=[[0,1],[0,-1],[1,0],[-1,0]] marked = [[False for _ in range(m)] for _ in range(n)] res = 0 for i in range(m): heapq.heappush(q, (a[0][i],0,i)) heapq.heappush(q, (a[n-1][i],n-1,i)) marked[0][i]=marked[n-1][i]=True for i in range(1,n-1): heapq.heappush(q, (a[i][0],i,0)) heapq.heappush(q, (a[i][m-1],i,m-1)) marked[i][0]=marked[i][m-1]=True while q: h,i,j=heapq.heappop(q) for di,dj in d: ii,jj=i+di,j+dj if 0<=ii雨の前に。

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.