Google面试题——蓄水问题

问题：

有一块矩形土地被划分成 N×M 个正方形小块，每块是一平方米。这些小块高低不平，每一小块地都有自己的高度H(i, j)米。水可以由任意一块地流向周围四个方向的四块地中，但不能直接流入对角相连的小块中。一场大雨后，许多低洼地方都积存了不少降水，求出它最多能积存多少立方米的降水么?

思路：

先看一维的情况如何处理：

预处理： 对每个格子求左边和右边的最高高度。 遍历每个格子： 找到左右最高高度的较小值，看是否大于这个格子的高度，如果大于则高度差就是这个格子存的水量。N个格子的积水量相加就是结果。

代码如下：（转自：https://github.com/codingtest/interview/blob/master/code2.cpp）

#include <stdio.h>#include <vector>#include <string>#include <vector>#include <list>#include <map>#include <set>#include <queue>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>using namespace std;//有一块矩形土地被划分成 N×M 个正方形小块，每块是一平方米。这些小块高低不平，//每一小块地都有自己的高度H(i, j)米。水可以由任意一块地流向周围四个方向的四块地中，//但不能直接流入对角相连的小块中。一场大雨后，许多低洼地方都积存了不少降水，求出它最多能积存多少立方米的降水么?int trap(int* a, int n){    if ( a == NULL || n == 0 )        return 0;    int* left = new int[n];    if ( left == NULL )           return 0;     int* right = new int[n];    if ( right == NULL )           return 0;    int maxL = 0;    for ( int i = 0 ; i < n-1; i++ )    {        left[i] = maxL;        maxL = max(maxL, a[i]);    }    int maxR = 0;    for ( int i = n-1; i >= 0; i-- )    {        right[i] = maxR;        maxR = max(maxR, a[i]);    }    int res = 0;    for ( int i = 0 ; i < n-1 ;i++)    {        int v = min(left[i], right[i]) - a[i];        if ( v > 0 )            res += v;    }    delete[] left;    delete[] right;    return res;}

一维的相对简单，那么二维的如何处理呢？

下面是http://weibo.com/lirenchen?key_word=%E6%B0%B4&is_search=1#1355214198625中的讨论的一些思路：

一种思路是找出四周最低的一块，从那开始灌水。先把四周的高度加入优先队列(priority queue, 或heap)，取出最低的向四周扩展，低于就注水，高于就加入堆。