Responsive image

问题 2861 --试题 F: 岛屿个数 (BFS)

2861: 试题 F: 岛屿个数 (BFS)

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

题目描述

小蓝得到了一副大小为 M × N 的格子地图,可以将其视作一个只包含字符‘0’(代表海水)和 ‘1’(代表陆地)的二维数组,地图之外可以视作全部是海水,每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。
在岛屿 A 所占据的格子中,如果可以从中选出 k 个不同的格子,使得他们的坐标能够组成一个这样的排列:(x0, y0),(x1, y1), . . . ,(xk−1, yk−1),其中(x(i+1)%k , y(i+1)%k) 是由 (xi , yi) 通过上/下/左/右移动一次得来的 (0 ≤ i ≤ k − 1),
此时这 k 个格子就构成了一个 “环”。如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部,此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿,C 又是 B 的子岛屿,那 C 也是 A 的子岛屿。
请问这个地图上共有多少个岛屿?在进行统计时不需要统计子岛屿的数目。

输入描述

第一行一个整数 T,表示有 T 组测试数据。
接下来输入 T 组数据。对于每组数据,第一行包含两个用空格分隔的整数M、N 表示地图大小;接下来输入 M 行,每行包含 N 个字符,字符只可能是‘0’ 或 ‘1’。

输出描述

对于每组数据,输出一行,包含一个整数表示答案。

样例输入

2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

样例输出

1
3

提示


对于第一组数据,包含两个岛屿,下面用不同的数字进行了区分:



01111



11001



10201



10001



11111



岛屿 2 在岛屿 1 的 “环” 内部,所以岛屿 2 是岛屿 1 的子岛屿,答案为 1。



对于第二组数据,包含三个岛屿,下面用不同的数字进行了区分:



111111



100001



020301



100001



111111



注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿,因为岛屿 1 和岛屿 2 中均没有“环”。



对于 30% 的评测用例,1 ≤ M, N ≤ 10。



对于 100% 的评测用例,1 ≤ T ≤ 10,1 ≤ M, N ≤ 50。

来源

[提交][状态]
ACM算法攻关部