How Many Islands?

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

Problem B: 島はいくつある?

この問題では,同じ大きさの正方形に区切られたメッシュ状の地図が与えられる. この地図は,ある海域を表しており,各正方形の領域が陸または海に対応する. 図B-1は地図の一例である.


図B-1:ある海域の地図

陸に対応する二つの正方形領域が,地図上で縦,横または斜め方向に隣接しているなら,一方から他方へ歩いて行くことができる. 陸に対応する二つの領域が同じ島に属するのは,一方から他方へ(一般には別の陸地を経由して)歩いて行ける時であり,またその時のみである. なお,この地図の海域は海で囲まれており,その外側へ歩いて出ることはできない.

与えられた地図を読み取り,この海域に島がいくつあるか数えるプログラムを作成して欲しい. たとえば,図B-1の地図には,全部で三つの島がある.

Input

入力はデータセットの列であり,各データセットは次のような形式で与えられる.

w h
c1,1 c1,2 ... c1,w
c2,1 c2,2 ... c2,w
...
ch,1 ch,2 ... ch,w

wh は地図の幅と高さを表す50以下の正の整数であり,地図は w×h 個の同じ大きさの正方形から構成される. wh の間は空白文字1個で区切られる.

ci, j は,0 または 1 であり,空白文字1個で区切られる. ci, j = 0 なら,地図上で左から i 番目,上か ら j 番目の正方形は海であり,ci, j = 1 なら陸である.

入力の終わりは,空白文字1個で区切られた2個のゼロのみからなる行で表される.

Output

各データセットに対し,島の個数を1行に出力せよ. それ以外の余計な文字を含んではいけない.

Sample Input

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

Output for the Sample Input

0
1
1
3
1
9

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2009-07-03
http://www.waseda.jp/assoc-icpc2009/en/