時間制限:1000ミリ秒
メモリ制限:65536KB
問題
ここ最近の雨で、農民ジョンの農場のいろんな場所に水溜りができてしまった。ジョンの農場はN x M個の正方形で構成される長方形で表すことができる(1 <= N <= 100; 1 <= M <= 100)。それぞれの正方形は水で濡れている('W')かもしくは乾いている('.')。ジョン農民はいくつの水溜りが自分の農場にあるのかを計算したい。
農場において、1つの濡れている状態にある正方形を見たときに、その正方形に隣接している8つの正方形もまた濡れている状態にあるとき、この二つの正方形の集合は水溜りであるといえる。また、2つの集合それぞれの中の正方形のうちどれかが互いに隣接している関係であれば、この二つの水溜りはまとめて一つの水溜りとして数える。
ジョン農民の農場の図が与えられたとき、彼の農場にいくつ水溜りがあるか決定せよ。
入力
・1行目: スペースで区切られた２つの整数 N と M が与えられる。
・2行目からN+1行目まで: 1行ごとにM個の文字がジョンの農場の行として与えられる。それぞれの文字は'W'もしくは'.'で与えられ、それぞれの間にはスペースは存在しない。
出力
・1行目：ジョンの農場内にある水溜りの総数。
入力の例
10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.
出力の例
3
ヒント
出力の詳細：3つの水溜りがある。それぞれは左上、左下、右側にある。
出典
USACO 2004 November