#526. Oil Deposits

Oil Deposits

GeoSurvComp\text{GeoSurvComp} 地质调查公司负责探测地下石油储藏。 GeoSurvComp\text{GeoSurvComp} 现在在一块矩形区域探测石油,并把这个大区域分成了很多小块。他们通过专业设备,来分析每个小块中是否蕴藏石油。如果这些蕴藏石油 的小方格相邻,那么他们被认为是同一油藏的一部分。在这块矩形区域,可能有很多油藏。你的任务是确定有多少不同的油藏。

输入格式

输入可能有多个矩形区域(即可能有多组测试)。每个矩形区域的起始行包含 nnmm ,表示行和列的数量,1n,m1001\le n,m\le 100 ,接下来是 nn 行,每行 mm 个字符。每个字符对应一个小方格,并且要么是 * ,代表没有油,要么是 @ ,表示有油。

输出格式

对于每一个矩形区域,输出油藏的数量。两个小方格是相邻的,当且仅当他们水平或者垂直或者对角线相邻(即8个方向)。 如果这些蕴藏石油 的小方格相邻,那么他们被认为是同一油藏的一部分。在这块矩形区域,可能有很多油藏。你的任务是确定有多少不同的油藏。

样例

样例输入

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

样例输出

0
1
2
2

来源

图论专题

数据范围与提示

  • 时间限制:1000ms1000\mathrm{ms}
  • 空间限制:65536KB65536\mathrm{KB}