塊を作ろう (paizaランク A 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

(電脳言語のオルダーソンループで出題された問題のヒント問題です。8 言語での解答コードと解説が用意されています。)

縦に H マス、横に W マスの長さの二次元グリッドが与えられます。それぞれのセルには、正負両方の値をとる整数が与えられます。

0 以上の整数が書かれた整数のみからなるセルをすべて選択したとき、連結成分がいくつできるかを求めてください。ただし、セルの集合が連結であるとは、セル集合内のある一つのセルから、上下左右に繋がっている集合内のセルを辿ることで、集合内の全てのセルを辿れることを指します。例えば、下の図では、黒いセルの集合は、左の 2 つの例では連結であり、右の 2 つの例では連結ではありません。

連結成分の個数は、左の 2 つの例では 1, 右上が 2, 右下が 3 となります。

入力例 1 では、連結成分の個数は 5 となります。

入力される値

H W
g_{1, 1} g_{1, 2} ... g_{1, W}
g_{2, 1} g_{2, 2} ... g_{2, W}
...
g_{H, 1} g_{H, 2} ... g_{H, W}

・ 1 行目に二次元グリッドの縦と横の長さを表す整数 H, W が半角スペース区切りで与えられます。
・続く H 行のうちの i 行目 (1 ≦ i ≦ H) には、W 個の整数が半角スペース区切りで与えられます。
　　・ i 行目の j 番目 (1 ≦ j ≦ W) の整数 g_{i, j} はグリッドの i 行 j 列目のセルに書かれている整数を表します。
・入力は合計で H + 1 行となり、入力値最終行の末尾に改行が１つ入ります。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: ・ 0 以上の整数が書かれたセルをすべて選択したときにできる連結成分の個数を出力してください。
・末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件: 全てのテストケースにおいて, 以下の条件を満たします。

・ 5 ≦ H ≦ 30
・ 5 ≦ W ≦ 30
・ -1,000 ≦ g_{i, j} ≦ 1,000 (1 ≦ i ≦ H, 1 ≦ j ≦ W)

入力例1: 5 5
8 4 -24 1 -2
-9 0 -7 -813 -13
2 -1 4 9 8
-6 0 -4 0 13
3 8 1 -11 813

出力例1: 5

問題一覧へ戻る