【題目描述】
Given?n?x?m?non-negative integers representing an elevation map 2d where the area of each cell is?1x1, compute how much water it is able to trap after raining.
給定n x m非負(fù)整數(shù)冀惭，表示二維的海拔地圖，每個(gè)單元的面積是1 x 1掀鹅，計(jì)算下雨后能捕到多少水散休。
【題目鏈接】
www.lintcode.com/en/problem/trapping-rain-water-ii/
【題目解析】
首先我們應(yīng)該能分析出，能裝水的底面肯定不能在邊界上乐尊，因?yàn)檫吔缟系狞c(diǎn)無法封閉戚丸，那么所有邊界上的點(diǎn)都可以加入queue，當(dāng)作BFS的啟動(dòng)點(diǎn)科吭，同時(shí)我們需要一個(gè)二維數(shù)組來標(biāo)記訪問過的點(diǎn)昏滴，訪問過的點(diǎn)我們用紅色來表示，那么如下圖所示：
我們?cè)傧胂攵匀耍趺礃涌梢猿晒Φ难b進(jìn)去水呢谣殊，是不是周圍的高度都應(yīng)該比當(dāng)前的高度高，形成一個(gè)凹槽才能裝水牺弄，而且裝水量取決于周圍最小的那個(gè)高度姻几，有點(diǎn)像木桶原理的感覺，那么為了模擬這種方法势告，我們采用模擬海平面上升的方法來做蛇捌，我們維護(hù)一個(gè)海平面高度mx，初始化為最小值咱台，從1開始往上升络拌，那么我們BFS遍歷的時(shí)候就需要從高度最小的格子開始遍歷，那么我們的queue就不能使用普通隊(duì)列了回溺，而是使用優(yōu)先級(jí)隊(duì)列春贸，將高度小的放在隊(duì)首混萝，最先取出，這樣我們就可以遍歷高度為1的三個(gè)格子萍恕，用綠色標(biāo)記出來了逸嘀，如下圖所示：
向周圍BFS搜索的條件是不能越界，且周圍格子未被訪問允粤，那么可以看出上面的第一個(gè)和最后一個(gè)綠格子無法進(jìn)行進(jìn)一步搜索崭倘，只有第一行中間那個(gè)綠格子可以搜索，其周圍有一個(gè)灰格子未被訪問過类垫，將其加入優(yōu)先隊(duì)列queue中司光，然后標(biāo)記為紅色，如下圖所示：
那么優(yōu)先隊(duì)列queue中高度為1的格子遍歷完了阔挠，此時(shí)海平面上升1飘庄，變?yōu)?脑蠕，此時(shí)我們遍歷優(yōu)先隊(duì)列queue中高度為2的格子购撼，有3個(gè)，如下圖綠色標(biāo)記所示：
我們發(fā)現(xiàn)這三個(gè)綠格子周圍的格子均已被訪問過了谴仙，所以不做任何操作迂求，海平面繼續(xù)上升，變?yōu)?晃跺，遍歷所有高度為4的格子揩局，如下圖綠色標(biāo)記所示：
由于我們沒有特別聲明高度相同的格子在優(yōu)先隊(duì)列queue中的順序，所以應(yīng)該是隨機(jī)的掀虎，其實(shí)誰先遍歷到都一樣凌盯，對(duì)結(jié)果沒啥影響，我們就假設(shè)第一行的兩個(gè)綠格子先遍歷到烹玉，那么那么周圍各有一個(gè)灰格子可以遍歷虫给，這兩個(gè)灰格子比海平面低了鹿响，可以存水了，把存水量算出來加入結(jié)果res中，如下圖所示：
上圖中這兩個(gè)遍歷到的藍(lán)格子會(huì)被加入優(yōu)先隊(duì)列queue中贸典，由于它們的高度小，所以下一次從優(yōu)先隊(duì)列queue中取格子時(shí)黍判，它們會(huì)被優(yōu)先遍歷到训措，那么左邊的那個(gè)藍(lán)格子進(jìn)行BFS搜索，就會(huì)遍歷到其左邊的那個(gè)灰格子瑞信，由于其高度小于海平面厉颤，也可以存水，將存水量算出來加入結(jié)果res中凡简，如下圖所示：
等兩個(gè)綠格子遍歷結(jié)束了逼友，它們會(huì)被標(biāo)記為紅色绩郎，藍(lán)格子遍歷會(huì)先被標(biāo)記紅色，然后加入優(yōu)先隊(duì)列queue中翁逞，由于其周圍格子全變成紅色了肋杖，所有不會(huì)有任何操作，如下圖所示：
此時(shí)所有的格子都標(biāo)記為紅色了挖函，海平面繼續(xù)上升状植，繼續(xù)遍歷完優(yōu)先隊(duì)列queue中的格子，不過已經(jīng)不會(huì)對(duì)結(jié)果有任何影響了怨喘，因?yàn)樗械母褡佣家呀?jīng)訪問過了津畸，此時(shí)等循環(huán)結(jié)束后返回res即可，
【參考答案】
