沉默雨巷

用户名：dotcpp0622054

访问量：2369

签　名：

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

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

　　自我简介：

蓝桥杯省二

TA的其他文章

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

你可能喜欢

两次DFS（染色法+合并）

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

原题链接：蓝桥杯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编程助手，随时响应你的问题：

　　评论区

赤鬼白柒

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

2024-04-10 13:12:00

devote 2024-04-10 13:57:58 |

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

赤鬼白柒 2024-04-10 21:53:03 |

没看清题，我还以为要算总岛屿数呢，尴尬

lyn 2024-04-12 10:12:53 |

sea数组的类型一定得是字符型嘛？

WWWsx

这个题解真的很好

2024-04-09 22:09:03

李世祥

厉害

2024-04-03 10:29:49

艾比露露

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

2024-04-01 14:54:21

碇真嗣

简明扼要，很好的题解！

2024-03-31 19:59:26

niubility

厉害

2024-01-26 17:07:40

uq_69632083412

很强啊

2023-07-21 11:00:59

沉默雨巷

TA的其他文章

你可能喜欢

用筛法求之N内的素数。（C++代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

P1001 （C++代码）

【出圈】（C语言代码）用单项循环链表

C二级辅导-分段函数（C语言代码）

两次DFS（染色法+合并）

评论区

精彩推荐

【亲和数】（C语言代码）

printf基础练习2 （C语言代码）

拆分位数（C语言代码）

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

WU-格式化数据输出（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

【计算球体积】（C语言代码）

C二级辅导-计负均正（C语言代码）

Quadratic Equation （C语言代码）

沉默雨巷

TA的其他文章

你可能喜欢

用筛法求之N内的素数。 （C++代码）

C语言训练-计算1~N之间所有奇数之和 （C语言代码）

P1001 （C++代码）

【出圈】 （C语言代码）用单项循环链表

C二级辅导-分段函数 （C语言代码）

两次DFS（染色法+合并）

评论区

精彩推荐

【亲和数】 （C语言代码）

printf基础练习2 （C语言代码）

拆分位数 （C语言代码）

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

WU-格式化数据输出 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

【计算球体积】 （C语言代码）

C二级辅导-计负均正 （C语言代码）

Quadratic Equation （C语言代码）

用筛法求之N内的素数。（C++代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

【出圈】（C语言代码）用单项循环链表

C二级辅导-分段函数（C语言代码）

　　评论区

【亲和数】（C语言代码）

拆分位数（C语言代码）

WU-格式化数据输出（C语言代码）

【计算球体积】（C语言代码）

C二级辅导-计负均正（C语言代码）