PKU2227-The Wedding Juicer

題目：http://poj.org/problem?id=2227
有一大小N*M的棋盤(地勢模型)，每個格子各有自己的高度
(高度B可以想像成有B塊1*1*1的正立方體堆起來的柱子)
積水會從上下左右四個方向、較低的地勢流走，而棋盤外的高度等同0
問最多有幾立方單位的積水


程式碼：http://codepad.org/kk79MtgN(感動，codepad終於能用了)
黑書例題
嗯...我想網路上不難找到「把外面一圈加入heap、然後floodfill」這種普通的答案
那就假設各位看過黑書、看過別人的解題報告還看不懂好了

我用自己的方式、自己的角度隨便記一下

首先，每個格子除了有自己的高度之外、也有自己的積水量：從0~999999999(最高減最低)
對任何棋盤我們可以果斷認定：最外圍一圈的積水量確定是0


[高度]

5 8 7 7
5 2 1 5
7 1 7 1
8 9 6 9
9 8 9 9

[積水表]

0 0 0 0

0 ? ? 0

0 ? ? 0

0 ? ? 0
0 0 0 0


可能不難蹦出一種想法：把每個?都試看看積水0、積水1、積水2…
其實我們的作法可說是這一類改進，只不過是基於這些「確定積水點」擴展的
首先看看第一步會取出最右排高度1、而四周有個高度7，無法積水，變成了…

0 0 0 0

0 ? ? 0

0 ? 0 0

0 ? ? 0
0 0 0 0
你瞧這些0就好像一座座聳立的高牆


接下來取最左排的高度5是下一步，擴展看到2的時候
關鍵來了：我們可以確定高度2這格的積水量是3
為什麼呢？因為高度5是這問號區域裡，最有可能漏水的格子(因為用最小堆取的) 此格積水如果大於3一定會漏出去、小於3也一定能加到3為止


於是據此更新答案
「想像確定的積水如結冰一般，變成了障礙物」
把這格的高度也當成5來看待



[高度]

5 8 7 7
5 5 1 5
7 1 7 1
8 9 6 9
9 8 9 9

[積水表]

0 0 0 0

0 3 ? 0

0 ? 0 0

0 ? ? 0
0 0 0 0


提供最後執行完以後的表格是這樣的：

[高度]

5 8 7 7
5 5 5 5
7 5 7 1
8 9 7 9
9 8 9 9

[積水表]

0 0 0 0

0 3 4 0

0 4 0 0

0 0 1 0
0 0 0 0


得到答案12