两次DFS（染色法+合并）

2673 阅读 12 评论 0 点赞

原题链接：蓝桥杯2023年第十四届省赛真题-岛屿个数

#解题思路
##- 在正式讲解这道题之前，我们先来学习一个比它**更简单**的问题

如果没有**“子岛屿”**这个题目限制，该如何判断有图中有几个岛屿？
其实很简单：我们遍历图中每一个点，遇到1说明遇到了岛屿，岛屿数加1，然后把其所在的**[四连通](https://blog.csdn.net/yewei11/article/details/50575593 "四连通")**区域（也就是整个岛屿，不知道这个概念的读者可点击**链接**学习）全部变成0（“**染色**”抹去这个岛屿，以免后面重复计算），继续这个过程直到没有1说明已经没有岛屿了。
相关题目可以去leetcode练习：[岛屿数量](http://leetcode.cn/problems/number-of-islands/ "岛屿数量")
##- 学会这个更简单的问题后，我们就可以正式开始这道题目的思考了

###我们关键是要解决一个**问题**：
怎么判断一个岛屿是另一个岛屿的“**子岛屿**”？
方法是**“合并”**
1. 首先我们用一个比地图**大一圈**的矩阵来存储这个地图（只需要大一圈就行，数组这样开sea[52][52]）
2. 由于地图外都是海水，所以先所有点都初始化为0（注意是字符'0'）
3. 然后，我们从(0,0)开始把所有相连的海水都标记为2（**第一次DFS**），这个过程之后图中所有剩下没有被更改的0一定在岛屿内部，（这次搜索要**八连通**，请读者自己思考为什么）；
4. 接下来我们再遍历一遍地图，把所有0都变成1，这样岛屿和其内部的子岛屿就“合为一体”了（请读者仔细分析）；
5. 所以，剩下来的问题就是上面那个更简单的问题了。（**第二次DFS**）

###其实还有一个关键的问题！那就是为什么我要开52x52的数组，开51x51的数组行不行？
答案是**不行**！只能多不能少。因为如果我们开51x51的数组，对于50x50那个海域地图，对于右下角的“**边角**”岛屿，即使不是子岛屿的“**包含**“关系，我们也**无法搜索进去**（请读者自己思考为什么）
所以我们要开数组52x52搜索一个更大的海域就能搜索进去了。
至此，问题解决！
#参考代码
    #include <bits/stdc++.h>
    using namespace std;
    #define For(i, x) for (int i = 0; i < x; i++)
    #define For1(i, x) for (int i = 1; i <= x; i++)
    int t, m, n;
    int next4[4][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }, // 四连通
        next8[8][2] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } }; // 八连通
    char sea[52][52]; // 至少52x52
    void dfs1(int x, int y) { // 第一次搜索
        sea[x][y] = '2';
        int newx, newy;
        For(i, 8) {
            newx = x + next8[i][0], newy = y + next8[i][1];
            if (0 <= newx && newx <= m + 1 && 0 <= newy && newy <= n + 1 && sea[newx][newy] == '0')
                dfs1(newx, newy);
        }
    }
    void dfs2(int x, int y) { // 第二次搜索
        sea[x][y] = '2';
        int newx, newy;
        For(i, 4) {
            newx = x + next4[i][0], newy = y + next4[i][1];
            if (1 <= newx && newx <= m && 1 <= newy && newy <= n && sea[newx][newy] == '1')
                dfs2(newx, newy);
        }
    }
    signed main() {
        cin >> t;
        while (t--) {
            int ans = 0;
            cin >> m >> n;
            For(i, m + 2) For(j, n + 2) sea[i][j] = '0'; // 初始化
            For1(i, m) For1(j, n) cin >> sea[i][j];
            dfs1(0, 0);
            For1(i, m) For1(j, n) if (sea[i][j] == '0') sea[i][j] = '1';
            For1(i, m) For1(j, n) if (sea[i][j] == '1') ans++, dfs2(i, j);
            cout << ans << endl;
        }
        return 0;
    }
##欢迎在评论区讨论交流！

0.0分

38 人评分

本文分类：题解列表
浏览次数：2673 次浏览
发布日期：2023-06-09 20:46:43
本文链接：https://blog.dotcpp.com/a/96875

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 12 条评论

H2430612014 2月前回复TA

夏天 3月前回复TA

简单，不错

lyn 9月前回复TA

@赤鬼白柒 sea数组的类型一定得是字符型嘛？

赤鬼白柒 9月前回复TA

@赤鬼白柒 没看清题，我还以为要算总岛屿数呢，尴尬

devote 9月前回复TA

@赤鬼白柒 没有被外层海水包围的岛屿一定是子岛屿，可以把它外面的海水变为陆地，就是将它和包含它的岛屿融合在一起，这样就不用计算子岛屿的数量了

赤鬼白柒 9月前回复TA

For1(i, m) For1(j, n) if (sea[i][j] == '0') sea[i][j] = '1';为什么要这样

WWWsx 9月前回复TA

这个题解真的很好

李世祥 10月前回复TA

厉害

艾比露露 10月前回复TA

第一次搜索的0，0位置需不需要判断是否岛屿再dfs呢

碇真嗣 10月前回复TA

简明扼要，很好的题解！

两次DFS（染色法+合并）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 12 条评论

发表评论 取消回复

评论列表共有 12 条评论

发表评论取消回复