两句话

用户名：uq_42709742140

访问量：3393

签　名：

等　　级
排　　名	2787
经　　验	2149
参赛次数	0
文章发表	37
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

Seq2Seq的学习总结
浏览：50

你可能喜欢

A+B for Input-Output Practice (I) （C++代码）

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

3153: 蓝桥杯2023年第十四届省赛真题-岛屿个数

　　作者: 两句话　　　　发表时间：2024-03-22 16:57:49 浏览：160　|　评论：0　

**知识点1：四连通及八连通区域**
四连通：即上下左右，递归遍历四连通区域可以把上下左右有一个以上格子重合的区域合并为一个。
八连通：米字型，递归遍历八连通区域可以把所有的存在一个公共点的格子合并为一个区域。
**知识点2：染色法**
合并区域时，从一个点出发，将这个点染成对应颜色，然后递归遍历这个点的四连通 / 八连通区域，把符合条件的点染成同样的颜色。该操作可以把相同区域合并，不同区域染成不同按颜色。
求区域个数时，采用四连通区域。

```cpp
#include<iostream>
using namespace std;

int n , m ;

char sea[52][52];	//给原矩阵增加边界
//四连通及八连通坐标变化
int next4[4][2] = {{-1 , 0} , {0 , 1} , {1 , 0} , {0 , -1}};
int next8[8][2] = {{-1 , 0} , {-1 , 1} , {0 , 1} , {1 , 1}  , {1 , 0} , {1 , -1} , {0 , -1} , {-1 , -1}};

void dfs_color(int x , int y)
{
    sea[x][y] = '2';
    int newx , newy;
    for(int i = 0;i < 8;i ++)
	{	//变化坐标{0 ，1}
        newx = x + next8[i][0] , newy = y + next8[i][1];
        if(newx >= 0 && newx <= n+1 && newy >= 0 && newy <= m+1 && sea[newx][newy] == '0')
            dfs_color(newx , newy);	//递归
    }
}

void dfs_num(int x , int y)
{
    sea[x][y] = '2';
    int newx , newy;
    for(int i = 0;i < 4;i ++)
    {
        newx = x + next4[i][0] , newy = y + next4[i][1];
        if(newx >= 1 && newx <= n && newy >= 1 && newy <= m && sea[newx][newy] == '1')
            dfs_num(newx , newy);
    }
}

int main()
{
    int t ;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        int ans = 0;
        for(int i = 0;i < n+2;i ++) 
            for(int j = 0;j < m+2;j ++)
                sea[i][j] = '0';	//将添加边界后的范围全部置为0

for(int i = 1;i <= n;i ++) 
            for(int j = 1;j <= m;j ++)
                cin>>sea[i][j];

dfs_color(0 , 0); //将大海部分染色成2

for(int i = 1;i <= n;i ++) 
            for(int j = 1;j <= m;j ++)//未被染色的大海区域完全处于某一海岛的内部
                if(sea[i][j] == '0') sea[i][j] = '1';//将内部全部合并为岛屿部分

for(int i = 1;i <= n;i ++) 
            for(int j = 1;j <= m;j ++)
                if(sea[i][j] == '1') 
                {
                    ans++;
                    dfs_num(i , j);	//将跟当前这块陆地相连的海岛全部合并
                }
        cout<<ans<<endl;
    }
    return 0;
}
```
**感觉dfs在某种意义上就是递归？**

0.0分

0 人评分

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

两句话

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (I) （C++代码）

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

【绝对值排序】（C语言代码）

最小公倍数（C语言代码）

sizeof的大作用（C语言代码）

3153: 蓝桥杯2023年第十四届省赛真题-岛屿个数

评论区

精彩推荐

字符串比较（C语言代码）

1231题解(注意理解“输入多个测试实例”)

JAM计数法（C语言代码）

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

小O的数字（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言描述——递归算法）

DNA （Java代码）

自编的贪吃蛇小游戏，代码装上easyx图形库就能运行。

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

Manchester- A+B for Input-Output Practice (II)

两句话

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (I) （C++代码）

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

【绝对值排序】 （C语言代码）

最小公倍数 （C语言代码）

sizeof的大作用 （C语言代码）

3153: 蓝桥杯2023年第十四届省赛真题-岛屿个数

评论区

精彩推荐

字符串比较 （C语言代码）

1231题解(注意理解“输入多个测试实例”)

JAM计数法 （C语言代码）

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

小O的数字 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言描述——递归算法）

DNA （Java代码）

自编的贪吃蛇小游戏，代码装上easyx图形库就能运行。

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

Manchester- A+B for Input-Output Practice (II)

【绝对值排序】（C语言代码）

最小公倍数（C语言代码）

sizeof的大作用（C语言代码）

　　评论区

字符串比较（C语言代码）

JAM计数法（C语言代码）

小O的数字（C语言代码）

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