第１６回日本情報オリンピック 予選 E - 尾根 (Ridge)
H*Wの高度マップが与えられる。水をあるマスに流すと、低い高度で隣接するマスに流れ、自マスからは水が消滅する。そのようなマスが2個以上隣接してる場合は、そのようなマス全てに水が流れる。周りがすべて自マスより高い高度の場合はそのマスに水がたまり、それ以上他に流れない。水を流したときに、最終的に2マス以上に水が貯まるマスを尾根と定義するときに、尾根は何個あるか？
2次元dp。マスをナンバリングし、マスごとに最終的に1個に流れるならばそのマスの番号(>0)、2個に流れるならば-1としてあるマスからdfsで状態を埋めていく。最初に流すマスを(1, 1)から(H, W)まですべて計算しても、dpテーブルは使いまわして良いので計算量はO(HW)になる。
