LeetCode 407. 接雨水 II
题目描述
给定一个 m x n
的矩阵,其中的值均为正整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。
说明:
m 和 n 都是小于110的整数。每一个单位的高度都大于0 且小于 20000。
示例:
给出如下 3x6 的高度图: [ [1,4,3,1,3,2], [3,2,1,3,2,4], [2,3,3,2,3,1] ] 返回 4。
如上图所示,这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
的状态。
下雨后,雨水将会被存储在这些方块中。总的接雨水量是4。
问题分析
此题用BFS来做。创建一个优先级队列,该队列中是将高度小的放在队首。先将四周一圈的格子加入队列中,并将这些格子的状态设为已访问过。下面开始BFS,从队列的头部取出元素,并用其高度更新海平面level,然后从该格子向四周寻找格子,如果某格子未被访问过,那么将其状态设为已访问过,然后判断如果其高度小于海平面,那么把它们的高度差加到ans中,否则不操作。接下来将该格子加入到优先级队列中。如此进行,当优先级队列为空时退出循环,返回ans。
代码实现
class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
if(heightMap.empty())
return 0;
int ans = 0;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int m = heightMap.size();
int n = heightMap[0].size();
int level = INT_MIN;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<vector<bool>> visited(m, vector<bool>(n, false));
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){
pq.push({heightMap[i][j], i * n + j});
visited[i][j] = true;
}
}
}
while(!pq.empty()){
auto a = pq.top();
pq.pop();
int height = a.first, row = a.second / n, col = a.second % n;
level = max(level, height);
for(int i = 0; i < 4; i++){
int x = row + dx[i], y = col + dy[i];
if(x < 0 || x == m || y < 0 || y == n || visited[x][y])
continue;
visited[x][y] = true;
if(heightMap[x][y] < level)
ans += level - heightMap[x][y];
pq.push({heightMap[x][y], x * n + y});
}
}
return ans;
}
};