No.697 池の数はいくつか

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 128 MB / 通常問題
タグ : / 解いたユーザー数 55
作問者 : yuki2006yuki2006
1 ProblemId : 1543

問題文

$H \times W$のフィールドが与えられます。フィールドには$0$と$1$だけがあります。
$0$が地面で$1$が水のマスです。
前後左右に連結している$1$同士をつないで最大のものが1つの池です。(斜めは連結ではありません)
(1マスでも池とします。)

このフィールドには池はいくつあるでしょうか?
フィールド外は地面とします。

(時間は多めに取っておりますが、関数呼び出しの回数・メモリ制限に気をつけてください。)
LL系では厳しいかもしれません。後日調整するかもしれません。

入力

$H\ W$
$A_{1,1} \dots A_{W,1}$
$\dots$
$A_{1,H} \dots A_{W,H}$

$1\le H,W \le 3000$
$A_{i,j}$は$0$か$1$

出力

池の数を出力してください。

サンプル

サンプル1
入力
4 3
1 0 1
0 1 0
1 0 1
0 1 0
出力
6

水が1マスのものが6つあります。
1マスでも池なので、池は6つあります。

サンプル2
入力
4 3
1 1 1
0 1 0
1 0 1
1 1 1
出力
2

水がくっついて池が2つです。

サンプル3
入力
3 4
0 0 0 0
0 0 0 0
0 0 0 0
出力
0

水がないときもあります。

サンプル4
入力
3 4
1 1 1 1
1 1 1 1
1 1 1 1
出力
1

全部水で池です。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。