岛屿个数

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

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$。