岛屿个数 DFS（蓝桥杯）

题目链接

蓝桥杯2023年第十四届省赛真题-岛屿个数 - C语言网

题目描述

小蓝得到了一副大小为 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寻找能被找到就不是子岛屿

 代码

#include <bits/stdc++.h> // 万能头文件
using namespace std;
 
int d1y[4] = {0, 0, 1, -1};
int d1x[4] = {1, -1, 0, 0};
int d2x[8] = {0, 0, 1, 1, 1, -1, -1, -1};
int d2y[8] = {1, -1, 0, 1, -1, 0, 1, -1};
// sz 每个岛屿的编号，ans 结果， grid 存图
int m, n, sz, ans, grid[55][55];
// check 记录岛屿是否出现过， vis 记录是否对岛屿进行过判断
bool check[1500], vis[55][55];
 
// 从2开始为每个岛屿标号
void dfs1(int i, int j)
{
    grid[i][j] = sz;
    for (int k = 0; k < 4; ++k)
    {
        int y = i + d1y[k];
        int x = j + d1x[k];
        if (y > 0 && y <= m && x > 0 && x <= n && grid[y][x] == 1)
            dfs1(y, x);
    }
}
 
// 从(0, 0)边界水, 开始搜索, 能找到的岛屿不是子岛屿
// 如果不增加两边水，当从陆地开始找水时, 需要判断是否是同一块岛屿继续搜索, 
// 和遇到其他岛屿停止当前搜索, 两种情况，较为复杂
void dfs2(int i, int j) 
{
    for (int k = 0; k < 8; ++k)
    {
        int y = i + d2y[k];
        int x = j + d2x[k];
        if (y >= 0 && y <= m + 1 && x >= 0 && x <= n + 1 && !vis[y][x])
        {
            vis[y][x] = true;
            if (grid[y][x] == 0)
            {
                dfs2(y, x);
            }
            else if (grid[y][x] >= 2 && !check[grid[y][x]])
            {
                check[grid[y][x]] = true;
                ans++;
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false); // 提高cin，cout速率
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        ans = 0, sz = 2;
        memset(grid, 0, sizeof(grid)); // 初始化
        memset(check, 0, sizeof(check));
        memset(vis, 0, sizeof(vis));
        cin >> m >> n;
        for (int i = 1; i <= m; ++i)
        {
            string s;
            cin >> s;
            for (int j = 1; j <= n; ++j) // 增加两边边界水的情况，存图
                grid[i][j] = s[j - 1] - '0';
        }
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (grid[i][j] == 1)
                {
                    dfs1(i, j); // 给岛屿标号
                    sz++; 
                }
            }
        }
        dfs2(0, 0); // 统计非子岛屿的个数
        cout << ans << endl;
    }
    return 0;
}