P9243 [蓝桥杯 2023 省 B] 岛屿个数
题目描述
小蓝得到了一副大小为 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。