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)，取出最低的向四周扩展，低于就注水，高于就加入堆。