沉默雨巷

用户名：dotcpp0622054

访问量：2521

签　名：

不在沉默中爆发，就在沉默中灭亡

等　　级
排　　名	13260
经　　验	932
参赛次数	0
文章发表	1
年　　龄	20
在职情况	学生
学　　校	河北科技大学
专　　业	软件工程

　　自我简介：

蓝桥杯省二

TA的其他文章

两次DFS（染色法+合并）
浏览：2471

你可能喜欢

两次DFS（染色法+合并）

　　作者: 沉默雨巷　　　　发表时间：2023-06-09 20:46:43 浏览：2471　|　评论：9　

原题链接：蓝桥杯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分

49 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

uq_69632083412

很强啊

2023-07-21 11:00:59

沉默雨巷

TA的其他文章

你可能喜欢

字符串的输入输出处理（C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言训练-求素数问题（C语言代码）

数字整除（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

两次DFS（染色法+合并）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

本人酷爱递归实现很多问题，这里也是

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）from DQM

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1071题解

1051（奇了怪了）

C语言训练-自守数问题（C语言代码）

上车人数（C语言代码）

生日日数（C语言代码）

沉默雨巷

TA的其他文章

你可能喜欢

字符串的输入输出处理 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言训练-求素数问题 （C语言代码）

数字整除 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

两次DFS（染色法+合并）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

本人酷爱递归实现很多问题，这里也是

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）from DQM

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1071题解

1051（奇了怪了）

C语言训练-自守数问题 （C语言代码）

上车人数 （C语言代码）

生日日数 （C语言代码）

字符串的输入输出处理（C语言代码）

C语言训练-求素数问题（C语言代码）

数字整除（C语言代码）

　　评论区

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言训练-自守数问题（C语言代码）

上车人数（C语言代码）

生日日数（C语言代码）