数羊群

Time Limit
1s
Memory Limit
32768KB
Judge Program
Standard
Ratio(Solve/Submit)
29.18%(314/1076)
Description:

草原上有一群羊,过一会又来了一群,请问现在有几群羊? 不会有人说是两群羊吧!为了防止有人将"一群羊"的概念曲解,现给出其概念. 将草原理想化为一个规则的矩形,且将它划分为一个个规则的单位小方块,每一小方块中恰好能容纳一头羊,假设羊a,则羊b与羊a为同一群羊应满足羊b所在的小方块和羊a所在的小方块相邻的8个方向,当然如果a和b是同一群,b和c是同一群,那么a和c也是同一群。 若小方块中有羊存在则这个小方块被标记为1,否则被标记为0.现给你一个矩形的小方块请数一数有几群羊?

Input:

输入有多组数据,每组数据的第一行为两个正整数n、k分别表示矩形草原所被划分小方块的行数和列数且1<=m、n<=120.接下来为一个m行n列的矩阵,矩阵的每个元素为1或者0. 输入以0 0结束,这一行不做任何处理.

Output:

每组测试数据对应一个输出为这个草原上羊的群数!

Sample Input:
1 1
1
1 5
11001
3 3
101
010
101
0 0
Sample Output:
1
2
1
Source:

李战平


Submit