この問題では,同じ大きさの正方形に区切られたメッシュ状の地図が与えられる. この地図は,ある海域を表しており,各正方形の領域が陸または海に対応する. 図B-1は地図の一例である.
陸に対応する二つの正方形領域が,地図上で縦,横または斜め方向に隣接しているなら,一方から他方へ歩いて行くことができる. 陸に対応する二つの領域が同じ島に属するのは,一方から他方へ(一般には別の陸地を経由して)歩いて行ける時であり,またその時のみである. なお,この地図の海域は海で囲まれており,その外側へ歩いて出ることはできない.
与えられた地図を読み取り,この海域に島がいくつあるか数えるプログラムを作成して欲しい. たとえば,図B-1の地図には,全部で三つの島がある.
入力はデータセットの列であり,各データセットは次のような形式で与えられる.
w h
c1,1 c1,2 ... c1,w
c2,1 c2,2 ... c2,w
...
ch,1 ch,2 ... ch,w
w と h は地図の幅と高さを表す50以下の正の整数であり,地図は w×h 個の同じ大きさの正方形から構成される. w と h の間は空白文字1個で区切られる.
ci, j は,0 または 1 であり,空白文字1個で区切られる. ci, j = 0 なら,地図上で左から i 番目,上か ら j 番目の正方形は海であり,ci, j = 1 なら陸である.
入力の終わりは,空白文字1個で区切られた2個のゼロのみからなる行で表される.
各データセットに対し,島の個数を1行に出力せよ. それ以外の余計な文字を含んではいけない.
1 1 0 2 2 0 1 1 0 3 2 1 1 1 1 1 1 5 4 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 5 4 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 5 5 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0
0 1 1 3 1 9