SRM371 Div2 1000

問題

グリッドに分けられた領域の高さが文字列で与えられる。
各高さは'a'-'z'で表され、'a'が一番低い。
この領域に雨が降った場合、いくつかの水溜りができてしまい水没する危険がある。
そこで、水溜りができないようにポンプをつけることにした。しかし、ポンプは高価なので、設置するポンプの数はできるだけ少なくしたい。
雨は現在の場所の高さ以下である隣接4近傍に流れる。
このとき、設置する最小のポンプ数を返す。

考え方

各座標を高さ順でソートする(構造体ST{int x,y,h;}などを作る)。
高さが低い場所から、その地点に水が流れ込むような領域をdfsで巡る(現在の地点の高さ以上の4近傍)。このとき、低い順に巡っていない(訪れていない)領域の個数をカウントすると水溜りの最低地点になるので、この数を返す。