SRM326 Div2 1000

問題

w*hのマスのそれぞれの高さが与えられる．そこに十分な量の雨が降ったとすると，各マスに溜まる水の総量はいくらか．
水は縦横4方向にのみ流れ，端のマスから外へは無限に水が流れていってしまう．

例
16661
61116
16661
の場合は，真ん中付近の111の部分に水が溜まるので，合計で(6-1)*3マス=15が答え．

考え方

「あるマスに溜まる水の量」＝「そのマスから端のマスまでの任意のルートで，そのルート中に出てくる高さの最大値，の中の最小値．
もし，そのマスの高さ以下のマスのみのルートがあるならば，そのルートから外に流れてしまう．

「メモ化DFS」とか「高さ決めうち」とかでも解けるみたいだけど，ここでは，「端のマスは必ず水がたまらない」という事実を使って，ヒープを使って周りから高さの低いマスの近傍を見ていく方法をまとめる．(前にheapの練習のときにほぼ同じ問題を解いたので，それの復習)

ヒープ：必ず子の数字が親よりも大きい二分木．O(log n)で最小値を取り出せる．priority_queueの逆(←最大値から取り出せる)．

まず，ヒープに端のマスの情報を入れていく．
ヒープで一番高さの低いマスiを取り出す．そのマスiの4近傍のマスjについて，
まだそのマスjをチェックしていないならば，

• マスiの高さ<=近傍マスjの高さ　→　マスjからマスiへ流れるので，新しい端としてそのマスjをヒープに登録
• マスiの高さ>近傍マスjの高さ　→　マスjは(周りのマスで一番高さが低い)マスiの高さまで水が溜まるので，その差分を答えに加え，溜まった高さを新しい高さとしてマスjをヒープに登録

をヒープの中身がなくなるまで繰り返す．

端のマスは必ず水が漏れるので高さが確定している．なので，高さが確定済みのものが常にヒープに入っていることになる．ヒープは高さが低いものから取り出していくので，その高さと比較することで水がどこまで溜まりうるかを確定していける．