leetcode407

正经解法比较复杂，这里贴出一个相对简单的解法。

题目描述

给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

1 <= m,n <= 200
0 <= heightMap[i][j] <= 2*10^4

示例1

输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。

示例2

输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10

思路分析

首先需要明确一点，该题中不存在“空洞”，否则数据不足以描述房屋的状态。即不存在以下（左视图）情况：

引理：沿水平方向任切一刀去除下层后，接水体积只会减少被切除部分中水的体积（若存在）。

解释：考虑使用一个锋利的铁板去切，切后仍用铁板托住上层，则上下两层的水均不会流出。

由引理，问题规模缩小。

代码实现（无优化）

记最高高度为MAXH，从第一层（从上往下数）开始切，for k 1 to MAXH，则切下来的上层可记为MAX(0,a[i][j]-MAXH+k)，对新的矩阵dfs元素为零的连通块，同时记录连通块大小。注意若连通块通向边界，则水流出，该连通块作废。遍历完第k层后k++，继续计算。

#include <cstdio>
#include <cstring>
#include <vector>

#define MAX(a,b) ((a)>(b)?(a):(b))
int dir[4][2] = {{0,1},{-1,0},{0,-1},{1,0}};
int a[203][203], m, n, MAXH = -1, ans;
bool vis[203][203];
using std::vector;

int dfs(int x,int y,bool& _myflag,int k){
    if(vis[x][y]) return 0;
    vis[x][y]=true;
    int cnt=1;
    if((x==1)||(x==m)||(y==1)||(y==n)){
        _myflag=false;
    }

    for(int p=0;p<4;p++){
        int nx=x+dir[p][0];
        int ny=y+dir[p][1];
        if((nx<1)||(nx>m)||(ny<1)||(ny>n)||vis[nx][ny])continue;
        if(MAX(0,a[nx][ny]-MAXH+k))continue;
        cnt+=dfs(nx,ny,_myflag,k);
    }
    return cnt;
}

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        ans = 0;
        MAXH = -1;
        auto it1 = heightMap.begin();
        m = heightMap.size(); 
        n = it1->size();

        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                a[i][j] = heightMap[i-1][j-1];
                MAXH = MAX(MAXH, a[i][j]);
            }
        }

        for(int k=1;k<=MAXH;k++){

            for(int i = 0; i < m+1; i++)
                for(int j = 0; j < n+1; j++)
                    vis[i][j] = false;

            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    if(MAX(0,a[i][j]-MAXH+k))vis[i][j]=true;
                    if(vis[i][j])continue;
                    bool myflag = true;
                    int tmp = dfs(i,j,myflag,k);
                    if(!myflag) continue;
                    ans += tmp;
                }
            }
        }
        return ans;
    }
};

这份代码的复杂度是 O(mn) 带着一个超大的常数，会超时。但是如果有一个层数不高、mn巨大的数据，或许这份代码会稍好一点。

所以要正经过题还是得看主流的解法。

优化思路

染色。

对于合法的连通块，不再进行 dfs，改为查询已记录位置下方是否有零。

对于通向边界的连通块，仍然需要 dfs. 若合法，则需将其加入合法颜色。

该改进的原理是：因不存在空洞，下一层的零元连通块是上层零元连通块的子集。