题目描述

小蓝得到了一副大小为 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。

dfs

0海水 1陆地 2外海 3岛屿
先将外围扩充一圈海水，从外海开始搜索，搜索到的陆地都是岛屿

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int t, n, m;
char d[55][55];
// 将海水改为外海
void dfs_sea(int x, int y)
{
    if (x >= 0 && x <= n + 1 && y >= 0 && y <= m + 1 && d[x][y] == 0)
    {
        d[x][y] = 2;
        // 8方向搜索海水
        for (int i = 0; i < 8; i++)
            dfs_sea(x + dx[i], y + dy[i]);
    }
}

void dfs_island(int x, int y)
{
    if (x >= 0 && x <= n + 1 && y >= 0 && y <= m + 1 && d[x][y] == 1)
    {
        d[x][y] = 3;
        // 4方向搜索陆地
        for (int i = 0; i < 8; i += 2)
            dfs_island(x + dx[i], y + dy[i]);
    }
}

int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        memset(d, 0, sizeof(d));
        // 外围扩充一圈海水
        for (int i = 0; i <= n + 1; i++)
            d[i][0] = d[i][m + 1] = 0;
        for (int i = 0; i <= m + 1; i++)
            d[0][i] = d[n + 1][i] = 0;
        // 输入地图
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                cin >> d[i][j];
                d[i][j] -= '0';
            }

        // 开始搜索
        dfs_sea(0, 0);
        int ans = 0;
        for (int i = 0; i <= n + 1; i++)
        {
            for (int j = 0; j <= m + 1; j++)
            {
                // 岛屿的旁边一定是外海
                if (d[i][j] == 1 && d[i - 1][j] == 2)
                {
                    dfs_island(i, j);
                    ans++;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}