No.697 池の数はいくつか
yuki2006問題文最終更新日: 2022-01-21 16:16:48
問題文
$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
全部水で池です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。