Shoreline

解説

各辺に対して水面と陸地の間にあるか判定してもよいが、ここではより実装が楽な方法を紹介する。

各陸地のマスには $4$ 本の辺があるので、陸地のマス数を $K$ とすると、辺の長さの合計は $4K$ である。

ただし、陸地同士が共有する辺は水面との境界ではないため、そのような辺については $2$ を引く必要がある。

したがって、辺を共有する陸地のマスの組数を $E$ とすると、答えは $4K-2E$ となる。

各マスを順に調べ、陸地であれば答えに $4$ を加え、上または左のマスも陸地であればそれぞれ $2$ を引けばよい。

以上より、 $O(HW)$ でこの問題を解くことができる。