问题2078--油田

2078: 油田

时间限制: 1 Sec  内存限制: 128 MB
提交: 41  解决: 17
[提交] [状态] [讨论版] [命题人:]

题目描述

某石油勘探公司正在按计划勘探地下油田资源，在一片长方形地域中工作。他们首先将该地域划分为许多小正方形区域，然后使用探测设备分别探测在每一小正方形区域内是否有油。含有油的区域被称为油田。如果两个油田相邻（在水平、垂直或对角线相邻），则它们是相同油藏的一部分。油藏可能非常大并可能包含许多油田（油田的个数不超过100）。你的工作是确定在这个长方形地域中包含多少不同的油藏。

输入

输入文件包含一个或多个长方形地域。每个地域的第1行都有两个正整数m 和n （1≤m,n ≤100），表示地域的行数和列数。如果m =0，则表示输入结束；否则此后有m 行，每行都有n 个字符。每个字符都对应一个正方形区域，字符*表示没有油，字符@表示有油。

输出

对于每个长方形地域，都单行输出油藏的个数。

样例输入 Copy 

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

样例输出 Copy 

0
1
2
2

来源/分类

图论基础 深度优先搜索算法 
[提交] [状态]