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），先把外圈所有点加入，然后取出高度最小的点，更新四周的点，注意标记这个点是否访问过，这个过程中记录墙增加的高度就是最后的积水量。
哎！咸鱼也是有梦想的！
int dx[] = {-, , , };
int dy[] = {, , , -};
class Solution {
public:
int trapRainWater(vector<vector<int>>& h) {
int n = h.size();
if(n == ) return ;
int m = h[].size();
vector<vector<bool> > vis(n, vector<bool>(m, ));
priority_queue<pair<int, pair<int, int> > > q;
for (int i = ; i < n; i++) {
for (int j = ; j < m; j++) {
if(i == || j == || i == n - || j == m - ) {
vis[i][j] = ;
q.push({-h[i][j], {i, j}});
}
}
}
long long res = ;
while(!q.empty()) {
int u = -q.top().first;
int ux = q.top().second.first;
int uy = q.top().second.second;
q.pop();
//cout << ux << " " << uy << " " << u << endl;
for (int i = ; i < ; i++) {
int x = ux + dx[i];
int y = uy + dy[i];
if(x < || y < || x >= n || y >= m || vis[x][y])
continue;
if(h[x][y] < u) {
res += u - h[x][y];
h[x][y] = u;
}
vis[x][y] = ;
q.push({-h[x][y],{x, y} });
}
}
return res;
}
};
int a[][];
bool v[][];
int dx[] = {, -, , };
int dy[] = {, , , -}; class Solution {
public:
bool in(int x, int y, int r, int c) {
return <= x && x < r && <= y && y < c;
}
int trapRainWater(vector<vector<int>>& h) {
priority_queue<pair<int, pair<int, int> > > q;
int m = h.size();
if(m == ) return ;
int n = h[].size(); memset(a, , sizeof a);
memset(v, , sizeof v);
for (int i = ; i < m; i++) {
for (int j = ; j < n; j++) {
if(i == || j == || i == m - || j == n - ) {
q.push(make_pair(-h[i][j], make_pair(i, j)));
a[i][j] = h[i][j];
v[i][j] = ;
}
}
}
// cout << n << " " << m << endl;
while(q.size()) {
pair<int, pair<int, int> > u = q.top();
q.pop();
int x = u.second.first;
int y = u.second.second;
for (int k = ; k < ; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (in(nx, ny, m, n) && !v[nx][ny]) {
if (h[nx][ny] < a[x][y]) {
a[nx][ny] = a[x][y];
} else {
a[nx][ny] = h[nx][ny];
}
v[nx][ny] = ;
q.push(make_pair(-a[nx][ny], make_pair(nx, ny)));
}
}
}
int ans = ;
for (int i = ; i < m; i++) {
for (int j = ; j < n; j++) {
ans += a[i][j] - h[i][j];
// printf("%d ", a[i][j]);
}
// printf("\n");
}
return ans;
}
};