[C] 深度优先搜索解决连通块/染色问题——求岛的个数

news/2024/4/21 1:11:39/

本文介绍用DFS解决连通块个数问题

有关dfs的介绍见另外一篇:不撞南墙不回头——深度优先搜索

例题

宝岛探险

题目描述

一个小岛由一个主岛和一些复附属岛屿组成,该岛使用一个二维矩阵表示,其中数字表示海拔,0表示海洋,1~9表示陆地。探险家乘坐飞机降落在(6,8)处,现在需要统计探险家降落的地图的小岛数量,我们将探险家降落点上下左右相连接的陆地视作同一个岛屿。

本文介绍DFS的解法,如果想了解用BFS解最大连通面积,看另一篇文章:层层递进——C语言实现广度优先搜索


测试样例:

10 10 6 8
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0

样例输出

4

解题思路

  • 这里startxstarty是多余的,请注意。
  • 这次要定义一个num,初始值为0,每次更换颜色之前-1,表示当前的颜色。
  • 对于每个点进行一次遍历,当这个点不是海洋并且没有被染色(值大于零)时,对这个点进行dfs搜索,将这个点所连通的地方全部染成一个“色”就是同一个数(这个时候被染色了,就是负值了~)
  • num取绝对值,就是岛的个数了。

题解

#include<stdio.h>
struct note
{int x;int y;
};
struct note que[400];
int head, tail;
int a[200][200];//地图
int book[200][200];
int next[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int max = 0;
int sum = 0;
int n, m, startx, starty;void dfs(int x, int y, int color)
{int k;int tx, ty;a[x][y] = color; // 对本格子染色for (k = 0; k < 4; k++){tx = x + next[k][0];ty = y + next[k][1];if (tx < 1 || tx > n || ty < 1 || ty > m)continue;if (a[tx][ty] > 0 && book[tx][ty] == 0){sum++;book[tx][ty] = 1;dfs(tx, ty, color);}}return;
}int main()
{int i, j;int num = 0;scanf("%d %d %d %d", &n, &m, &startx, &starty);for (i = 1; i <= n; i++)for (j = 1; j <= m; j++)scanf("%d", &a[i][j]);for (i = 1; i <= n; i++){for (j = 1; j <= m; j++){if (a[i][j] > 0){num--;// num表示色号,并且是负数book[i][j] = 1;sum = 1;dfs(i, j, num);if (sum > max){max = sum;}}}}for (i = 1; i <= n; i++){for (j = 1; j <= m; j++){printf("%3d", a[i][j]);}printf("\n");}printf("有%d个小岛\n", -num);printf("最大的岛的面积是%d\n", max);return 0;
}/*
10 10 6 8
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0*/

运行结果:
在这里插入图片描述


http://www.ppmy.cn/news/607584.html

相关文章

大数据必学Java基础(十九):运算符总结

文章目录 运算符总结 一、汇总说明 二、优先级别 运算符总结 一、汇总说明

Docker教程

Docker 能解决的问题 ⾸先&#xff0c;我们先来看⼏个问题&#xff1a; 1. 合作开发的时候&#xff0c;在本机可以运⾏&#xff0c;在别⼈的电脑上跑不起来。 这⾥我们以 Java Web 应⽤程序为例&#xff0c;⼀个 Java Web 应⽤程序涉及很多东⻄&#xff0c;⽐如 JDK 、 Tomc…

梯度提升决策树(GBDT)与XGBoost、LightGBM

20211224 【机器学习算法总结】XGBoost_yyy430的博客-CSDN博客_xgboost xgboost参数 默认&#xff1a;auto。XGBoost中使用的树构造算法。可选项&#xff1a;auto&#xff0c;exact&#xff0c;approx&#xff0c;hist&#xff0c;gpu_exact&#xff0c;gpu_hist。分布式和外部…

TensorFlow算子融合

TensorFlow算子融合 • TensorFlow的特点&#xff1a; o 真正的可移植性 o 引入各种计算设备的支持&#xff0c;包括CPU&#xff0c;GPU&#xff0c;以及能够很好的运行在各种系统的移动端 o 多语言支持 o 支持C&#xff0c;python&#xff0c;R语言等 o 高度的灵活性和效率 o …

大数据必学Java基础(二十):流程控制的引入和if语句介绍

文章目录 流程控制的引入和if语句介绍 一、引入 1、流程控制的作用 2、控制语句的分类

计算机主机网关的作用是什么意思,电脑网关是什么意思?

上次我们发布了局域网ip地址不够用怎么解决&#xff1f;很多朋友多次问到什么是网关、dns、子网掩码&#xff0c;它有什么作用&#xff0c;确实&#xff0c;我们平时在网络中总是在不断的提到网关&#xff0c;却很少真正的去了解它。例&#xff1a;一、什么是网关一、什么是网关…

[C] [编程题]连通块(DFS解决)

时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒空间限制&#xff1a;C/C 256M&#xff0c;其他语言512M 来源&#xff1a;牛客网 金山办公2020校招服务端开发工程师笔试题&#xff08;一&#xff09; 题目描述 给一个01矩阵&#xff0c;1代表是陆地&#xff0c;0代表海洋…

Graph Representation 图神经网络

Graph Representation 图神经网络 图表示学习(representation learning)——图神经网络框架&#xff0c;主要涉及PyG、DGL、Euler、NeuGraph和AliGraph五个框架。除了NeuGraph没有开源外&#xff0c;其它框架都已开源。 Pytorch Geometric (PyG) PyG在PyTorch上实现&#xff…

中国矿业大学计算机学院机房,2020年中国矿业大学计算机学院初试自命题科目考试大纲-数据结构...

一、 考试目的与要求目的&#xff1a;通过本科目的考试&#xff0c;考察计算机专业人员对《数据结构》课程内容的理解和掌握程度以及相关算法编写能力。要求&#xff1a;掌握各种基本概念和术语&#xff0c;掌握算法描述和分析的方法。重点是掌握数据结构的逻辑结构、存储结构及…

Drone Settings 页面没有 Trusted踩坑

前言 懒得写了&#xff0c;等有时间再搞 解决方案 1.在docker执行的时候或则docker-compose.yml 中加上DRONE_USER_CREATE 和 DRONE_ADMIN&#xff0c;具体的参考如下 environment:...- DRONE_ADMINadmin- DRONE_USER_CREATEusername:admin,admin:true 2.如果上面方法用了还…

[C] 图的深度优先遍历

图的DFS遍历 首先我们需要知道什么是图 简单地说&#xff0c;图就是由一些小圆点&#xff08;称为顶点&#xff09;和连接这些小圆点的直线&#xff08;称为边&#xff09;组成的。例如上图是由五个顶点&#xff08;编号为1&#xff0c;2&#xff0c;3&#xff0c;4&#xff…

数据湖(十三):Spark与Iceberg整合DDL操作

文章目录 Spark与Iceberg整合DDL操作 一、​​​​​​​CREATE TABLE 创建表

英特尔 QLC 3D NAND 数据存储

英特尔 QLC 3D NAND 数据存储 NAND是什么 由于SSD固态硬盘的普及&#xff0c;NAND这个词逐渐进入用户们的视线。许多厂商都在产品宣传中提到3D NAND颗粒等词汇&#xff0c;对于普通用户来讲&#xff0c;完全不知道这个词是什么意思&#xff0c;只是有一种不明觉厉的感觉&#x…

大数据必学Java基础(二十一):Switch多分支结构介绍

文章目录 Switch多分支结构介绍 一、switch多分支结构(多值情况) 二、练习 Switch多分支结构介绍 一、switch多分支结构(多值情况)

计算机应用专业能评自动化工程师吗,报考自动化控制工程师中级职称需要哪些条件?...

2019-05-15 16:22辛培勇自动化专业&#xff0c;考个自动化工程师&#xff0c;电气自动化工程师等资格证都挺好。主要从事与电气工程有关的系统运行、自动控制、电力电子技术、信息处理、试验分析、研制开发、经济管理以及电子与计算机技术应用等领域的工作。本专业培养的学生具…

[C] 图的广度优先遍历

图的广度优先遍历 我一直觉得图的遍历没有地图类型的题目难&#xff0c;遍历嘛&#xff0c;每个点都走一遍就行了。 但是给定地图求面积啊&#xff0c;数量啊的那种题目&#xff0c;花样挺多的。 图的遍历真挺难把人绕晕的&#xff0c;关于广度优先&#xff0c;理解好层层递进这…

数据湖(十四):Spark与Iceberg整合查询操作

文章目录 Spark与Iceberg整合查询操作 一、DataFrame API加载Iceberg中的数据 二、查询表快照

SpringBoot项目中功能集成的方式

原文合集地址如下&#xff0c;有需要的朋友可以关注 本文地址 合集地址 SpringBoot项目中功能集成的方式 接口集成 基于HTTP协议的集成方式 协议和通信 HTTP是一种基于客户端-服务器模型的协议。确定使用的HTTP版本&#xff08;如HTTP/1.1或HTTP/2&#xff09;以及通信过…

计算机考试机试题目word文档,计算机考试 word

2006年教师职称计算机考试试题(第5章)第五章Word 2000文字处理软件1、打开WORD文档一般是指(B)A把文档的内容从内存中读入并在屏幕上显示出来B把文档的内容从磁盘上调入内存并在屏幕上显示出来C为指定的文档开设一个新的空白文档窗口  D显示并打印指定的文档内容2、关于WORD的…

TVM darknet yolov3算子优化与量化代码的配置方法

TVM darknet yolov3算子优化与量化代码的配置方法 使用以下接口函数  tvm.relay.optimize  quantize.quantize 实际代码&#xff1a; convert nnvm to relay print(“convert nnvm symbols into relay function…”) #from nnvm.to_relay import to_relay func, params …