首页 > 代码库 > [leetcode] 407. Trapping Rain Water II
[leetcode] 407. Trapping Rain Water II
https://leetcode.com/contest/6/problems/trapping-rain-water-ii/
看到这题，我很高兴，因为我做过！哈哈！其实我现在也写不出来，知道大概思想。
这题是google apactest 2017 round A 的第二题。https://code.google.com/codejam/contest/11274486/dashboard#s=p1
然后，简单一次调试，就ac了。不知道这算不算作弊，做完，我就看见什么instruction，说是可以看别人代码，然后举报作弊，有点怕！
分析：这题算是动态规划吧，读懂题意后，（其实这个题目描述的不清楚啊，图的示例倒是挺好），可以观察，可以从外圈往里圈缩，因为这个过程墙的高度是非递减的，然后，你应该想到用优先队列（priority_queue或者set，又是讨厌的set），先把外圈所有点加入，然后取出高度最小的点，更新四周的点，注意标记这个点是否访问过，这个过程中记录墙增加的高度就是最后的积水量。
哎！咸鱼也是有梦想的！
1 int a[120][120]; 2 bool v[120][120]; 3 int dx[] = {1, -1, 0, 0}; 4 int dy[] = {0, 0, 1, -1}; 5 6 class Solution { 7 public: 8 bool in(int x, int y, int r, int c) { 9 return 0 <= x && x < r && 0 <= y && y < c;10 }11 int trapRainWater(vector<vector<int>>& h) {12 priority_queue<pair<int, pair<int, int> > > q;13 int m = h.size();14 if(m == 0) return 0;15 int n = h[0].size();16 17 memset(a, 0, sizeof a);18 memset(v, 0, sizeof v);19 for (int i = 0; i < m; i++) {20 for (int j = 0; j < n; j++) {21 if(i == 0 || j == 0 || i == m - 1 || j == n - 1) {22 q.push(make_pair(-h[i][j], make_pair(i, j)));23 a[i][j] = h[i][j];24 v[i][j] = 1;25 }26 }27 }28 // cout << n << " " << m << endl;29 while(q.size()) {30 pair<int, pair<int, int> > u = q.top();31 q.pop();32 int x = u.second.first;33 int y = u.second.second;34 for (int k = 0; k < 4; k++) {35 int nx = x + dx[k];36 int ny = y + dy[k];37 if (in(nx, ny, m, n) && !v[nx][ny]) {38 if (h[nx][ny] < a[x][y]) {39 a[nx][ny] = a[x][y];40 } else {41 a[nx][ny] = h[nx][ny];42 }43 v[nx][ny] = 1;44 q.push(make_pair(-a[nx][ny], make_pair(nx, ny)));45 }46 }47 }48 int ans = 0;49 for (int i = 0; i < m; i++) {50 for (int j = 0; j < n; j++) {51 ans += a[i][j] - h[i][j];52 // printf("%d ", a[i][j]);53 }54 // printf("\n");55 }56 return ans;57 }58 };
[leetcode] 407. Trapping Rain Water II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。