C++ | Leetcode C++题解之第407题接雨水II

题目：

题解：

1. class Solution {
2. public:
3.     int trapRainWater(vector<vector<int>>& heightMap) {
4.         int m = heightMap.size(), n = heightMap[0].size();
5.         int maxHeight = 0;
6.         int dirs[] = {-1, 0, 1, 0, -1};
8.         for (int i = 0; i < m; ++i) {
9.             maxHeight = max(maxHeight, *max_element(heightMap[i].begin(), heightMap[i].end()));
10.         }
11.         vector<vector<int>> water(m, vector<int>(n, maxHeight));
12.         queue<pair<int,int>> qu;
13.         for (int i = 0; i < m; ++i) {
14.             for (int j = 0; j < n; ++j) {
15.                 if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
16.                     if (water[i][j] > heightMap[i][j]) {
17.                         water[i][j] = heightMap[i][j];
18.                         qu.push(make_pair(i, j));
19.                     }
20.                 }
21.             }
22.         }        
23.         while (!qu.empty()) {
24.             int x = qu.front().first, y = qu.front().second;
25.             qu.pop();
26.             for (int i = 0; i < 4; ++i) {
27.                 int nx = x + dirs[i], ny = y + dirs[i + 1];
28.                 if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
29.                     continue;
30.                 }
31.                 if (water[x][y] < water[nx][ny] && water[nx][ny] > heightMap[nx][ny]) {
32.                     water[nx][ny] = max(water[x][y], heightMap[nx][ny]);
33.                     qu.push(make_pair(nx, ny));
34.                 }
35.             }
36.         }
38.         int res = 0;
39.         for (int i = 0; i < m; ++i) {
40.             for (int j = 0; j < n; ++j) {
41.                 res += water[i][j] - heightMap[i][j];
42.             }
43.         }
44.         return res;
45.     }
46. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。