407. Trapping Rain Water II (Hard)

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.

Solution 1: BFS + Priority Queue

Time Complexity: $$O(NlogN)$$ 86 ms

这道题是之前那道Trapping Rain Water的拓展，由2D变3D了，感觉很叼。但其实解法跟之前的完全不同了，之前那道题由于是二维的，我们可以用双指针来做，而这道三维的，我们需要用BFS来做

首先我们应该能分析出，能装水的底面肯定不能在边界上，因为边界上的点无法封闭，那么所有边界上的点都可以加入queue，当作BFS的启动点，同时我们需要一个二维数组来标记访问过的点。

每次从queue里取出height最低的点，并更新一下高度最大值。 找到四周未被访问过的点，如果该点的height小于高度最大值，把差值加入res。把这些为访问过的点标记为visited，并且放入queue里，直到queue为空。

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.size() == 0) return 0;
        int n = heightMap.size(), m = heightMap[0].size();
        if (n <= 2 || m <= 2) return 0;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
        bool visited[n][m] = {false};

        for (int i = 0; i < m; ++i) {
            visited[0][i] = true;
            visited[n-1][i] = true;
            q.push({heightMap[0][i], i});
            q.push({heightMap[n-1][i], (n-1)*m+i});
        }
        for (int i = 1; i < n-1; ++i) {
            visited[i][0] = true;
            visited[i][m-1] = true;
            q.push({heightMap[i][0], i*m});
            q.push({heightMap[i][m-1], (i+1)*m-1});
        }
        int res = 0, level = 0;
        int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
        while(!q.empty()) {
            auto t = q.top(); q.pop();
            level = max(level, t.first);
            for (int i = 0; i < 4; ++i) {
                int x = t.second/m+dx[i], y = t.second%m+dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y]) continue;
                visited[x][y] = true;
                if (heightMap[x][y] < level) res += level-heightMap[x][y];
                q.push({heightMap[x][y], x*m+y});
            }
        }

        return res;
    }
};

Soltuion 2: Dijkstra

等有空再写吧，不容易理解

Time Complexity: $$O(NM * max(log N, log M))$$

Construct a graph G = (V, E):

V: all cells plus a dummy vertex v, corresponding to the outside region

E: if cell(i, j) is adjacent to cell(i', j'), then add an direct edge from (i, j) to (i', j') with weight heightMap[i][j]

add an edge with 0 weight from any boundary cell to dummy vertex v.

The weight of a path is defined as the weight of the heaviest edge along it. Then for any cell(i, j), the height of water it can save is equal to the weight, denoted by dist(i, j), of the shortest path from (i, j) to v.

Note: if the weight is equal to heightMap[i][j], no water can be accumulated at that particular position.

We want to compute the dist(i, j) for all pairs of (i, j). Here, we have multiple sources and one destination, but this problem essentially can be solved using one pass of Dijkstra algorithm if we reverse the directions of all edges. The graph is sparse, i.e. there are O(rc) edges, resulting an O(rc log(rc)) = O(rc max(log r, log c)) runtime and using O(rc) space.