leetcode407. 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.

解题思路：

类比于trapped rain water, 上一个是一维的数组，而这一个是二维的矩阵。

所以其可能的情况就会比一维数组更为复杂

一开始可能会想，对该格子所在的行和列找边界比较，但实际上这种想法是错误的

如图所示：

对于8所在的格子，如果只看所在的行和列的话，边界为13， 看起来能盛（13-8）的水，但是实际上，这些水都会从虚线所指方向流走。

所以我们要找边界，应该是从整个矩阵的外围找边界。

所以我们可以使用最小堆(priority_queue)来解决这个问题，同时用一个二维矩阵记录是否访问过

首先把外围的一圈放进堆里，然后取出最小的，尝试上下左右四个方向走，找到未访问过的点，然后访问它，并比较它与当前最大值的墙的高度

然后将这一点标记为访问同时将其压到堆里

代码：

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if(heightMap.empty())
            return 0;
        int m = heightMap.size();
        int n = heightMap[0].size();
        int ret = 0;
        int mx = INT_MIN;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> q;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<vector<int>> dir{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
        for(int i =0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 || j == 0 || i == m-1 || j == n-1){
                    q.push({heightMap[i][j], i*n + j});
                    visited[i][j] = true;
                }
            }
        }
        while(!q.empty()){
            auto t = q.top();
            q.pop();
            int h = t.first;
            int r = t.second / n;
            int c = t.second % n;
            mx = max(h, mx);
            for(int i = 0; i < dir.size(); i++){
                int x = r + dir[i][0];
                int y = c + dir[i][1];
                if(x < 0 || x >= m || y < 0 || y >= n || visited[x][y])
                    continue;
                visited[x][y] = true;
                if(heightMap[x][y] < mx)
                    ret += (mx - heightMap[x][y]);
                q.push({heightMap[x][y], x * n + y});
            }
        }
        return ret;

    }
};

参考：

http://www.cnblogs.com/grandyang/p/5928987.html

c++: pair

c++: greater

c++: priority_queue