(蓝桥杯)岛屿个数

问题形貌

小蓝得到了一副大小为 M×NM×N 的格子地图，可以将其视作一个只包罗字符 '0'（代表海水）和 '1'（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 '1' 相连接而形成。
在岛屿 AA 所占据的格子中，如果可以从中选出 kk 个差别的格子，使得他们的坐标可以或许组成一个这样的分列：(x0,y0),(x1,y1),…,(xk−1,yk−1)(x0​,y0​),(x1​,y1​),…,(xk−1​,yk−1​)，此中 (xi+1modk,yi+1modk)(xi+1modk​,yi+1modk​) 是由 (xi,yi)(xi​,yi​) 通过上/下/左/右移动一次得来的 (0≤i≤k−1)(0≤i≤k−1)，此时这 kk 个格子就构成了一个“环”。如果另一个岛屿 BB 所占据的格子全部位于这个“环”内部，此时我们将岛屿 BB 视作是岛屿 AA 的子岛屿。若 BB 是 AA 的子岛屿，CC 又是 BB 的子岛屿，那 CC 也是 AA 的子岛屿。
请问这个地图上共有多少个岛屿？在举行统计时不需要统计子岛屿的数目。
输入格式

第一行一个整数 TT，表示有 TT 组测试数据。
接下来输入 TT 组数据。对于每组数据，第一行包罗两个用空格分隔的整数 MM、NN 表示地图大小；接下来输入 MM 行，每行包罗 NN 个字符，字符只可能是 '0' 或 '1'。
输出格式

对于每组数据，输出一行，包罗一个整数表示答案。
样例输入

2. 2
3. 5 5
4. 01111
5. 11001
6. 10101
7. 10001
8. 11111
9. 5 6
10. 111111
11. 100001
12. 010101
13. 100001
14. 111111

复制代码

样例输出

2. 1
3. 3

复制代码

样例分析

对于第一组数据，包罗两个岛屿，下面用差别的数字举行了区分：

2. 01111
3. 11001
4. 10201
5. 10001
6. 11111

复制代码

岛屿 22 在岛屿 11 的“环”内部，所以岛屿 22 是岛屿 11 的子岛屿，答案为 11。
对于第二组数据，包罗三个岛屿，下面用差别的数字举行了区分：

2. 111111
3. 100001
4. 020301
5. 100001
6. 111111

复制代码

注意岛屿 33 并不是岛屿 11 大概岛屿 22 的子岛屿，因为岛屿 11 和岛屿 22 中均没有“环”。
评测用例规模与约定

对于 3030 的评测用例，1≤M,N≤101≤M,N≤10。
对于 100100 的评测用例，1≤T≤101≤T≤10，1≤M,N≤501≤M,N≤50。

2. #include<bits/stdc++.h>
3. using namespace std;
5. int dx[4] = {1, 0, -1, 0};
6. int dy[4] = {0, 1, 0, -1};
8. int dx0[8] = {1, 0, -1, 0, 1, -1, 1, -1};
9. int dy0[8] = {0, 1, 0, -1, -1, 1, 1, -1};
11. int t;
12. int n, m;
13. char e[100][100];
14. bool bk[100][100];
15. bool bk0[100][100];
17. bool check(int x, int y) {
18.         return x >= 1 && x <= n && y >= 1 && y <= m && !bk[x][y] && e[x][y] == '1';
19. }
21. bool check0(int x, int y) {
22.         return x >= 0 && x <= n + 1 && y >= 0 && y <= m + 1 && !bk0[x][y] && e[x][y] == '0';
23. }
25. void dfs0(int x, int y) {
27.         bk0[x][y] = true;
28.         for (int i = 0; i < 8; i++) {
29.                 int nx = dx0[i] + x;
30.                 int ny = dy0[i] + y;
32.                 if (check0(nx, ny)) {
33.                         dfs0(nx, ny);
34.                 }
35.         }
36.         return;
37. }
39. void dfs(int x, int y) {
41.         bk[x][y] = true;
42.         for (int i = 0; i < 4; i++) {
43.                 int nx = dx[i] + x;
44.                 int ny = dy[i] + y;
46.                 if (check(nx, ny)) {
47.                         dfs(nx, ny);
48.                 }
49.         }
50.         return;
51. }
53. int main() {
54.         cin >> t;
55.         while (t--) {
56.                 int ans = 0;
57.                 cin >> n >> m;
58.                 memset(bk, 0, sizeof(bk));
59.                 memset(bk0, 0, sizeof(bk0));
60.                 for (int i = 0; i <= n + 1; i++) {
61.                         for (int j = 0; j <= m + 1; j++) {
62.                                 if (i >= 1 && i <= n && j >= 1 && j <= m) {
63.                                         cin >> e[i][j];
64.                                 } else {
65.                                         e[i][j] = '0';
66.                                 }
67.                         }
68.                 }
70.         dfs0(0, 0);
71.                 for (int i = 1; i <= n; i++) {
72.                         for (int j = 1; j <= m; j++) {
73.                                 if (!bk[i][j] && e[i][j] == '1') {
74.                                         dfs(i, j);
75.                                         if (bk0[i + 1][j + 1] || bk0[i][j + 1] || bk0[i + 1][j] || bk0[i - 1][j] || bk0[i][j - 1] || bk0[i - 1][j - 1] || bk0[i - 1][j + 1] || bk0[i][j - 1] || bk0[i + 1][j - 1]) {
76.                                                 ans++;
77.                                         }
78.                                 }
79.                         }
80.                 }
82.                 cout << ans << endl;
84.         }
86.         return 0;
87. }

复制代码