当前位置: 首页 > news >正文

代码随想录算法训练营第六十五天|KM99. 岛屿数量——深搜、KM99. 岛屿数量——广搜、KM100. 岛屿的最大面积

代码随想录算法训练营第六十五天

KM99. 岛屿数量——深搜

题目链接:KM99. 岛屿数量
使用递归深度搜索,将每次遇到的岛屿上下左右记录为已经到过,如果遇到没到过的说明它上下左右不是之间遍历过的岛屿,结果计数+1。最后统计计数即可知道有多少个岛屿

#include <iostream>
#include <vector>
using namespace std;int dir[4][2] = {{0, 1}, //列+1,右移{1, 0}, //行+1,下移{-1, 0},//行-1,上移{0, -1} //列-1,左移
};
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {if (visited[x][y] || grid[x][y] == 0) return;visited[x][y] = true;for (int i = 0; i < 4; i++) {int next_x = x + dir[i][0];int next_y = y + dir[i][1];if (next_x < 0 || next_x >= grid.size() || next_y < 0 || next_y >= grid[0].size()) continue;// 越界了,直接跳过dfs(grid, visited, next_x, next_y);}
};int main() {int N, M;std::cin >> N >> M;vector<vector<int>> grid(N, vector<int>(M, 0));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(N, vector<bool>(M, false));int result = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (!visited[i][j] && grid[i][j] == 1) {result++;dfs(grid, visited, i, j);}}}std::cout << result << std::endl;return 0;
};

KM99. 岛屿数量——广搜

题目链接:KM99. 岛屿数量
使用广度搜索,将每次遇到的岛屿上下左右记录为已经到过,如果遇到没到过的说明它上下左右不是之间遍历过的岛屿,结果计数+1。最后统计计数即可知道有多少个岛屿


#include<iostream>
#include<vector>
#include<queue>using namespace std;int dir[4][2] = {{0,  1}, //列+1,右移{1,  0}, //行+1,下移{-1, 0},//行-1,上移{0,  -1} //列-1,左移
};void bfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y) {queue<pair<int, int>> que;que.push({x, y});visited[x][y] = true;while (!que.empty()) {pair<int, int> cur = que.front();que.pop();for (int i = 0; i < 4; i++) {int next_x = cur.first + dir[i][0];int next_y = cur.second + dir[i][1];if (next_x < 0 || next_x >= grid.size() || next_y < 0 || next_y >= grid[0].size())continue;if (grid[next_x][next_y] == 1 && !visited[next_x][next_y]) {visited[next_x][next_y] = true;que.push({next_x, next_y});}}}
};int main() {int N, M;std::cin >> N >> M;vector<vector<int>> grid(N, vector<int>(M, 0));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(N, vector<bool>(M, false));int result = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (!visited[i][j] && grid[i][j] == 1) {result++;bfs(grid, visited, i, j);}}}std::cout << result << std::endl;return 0;
};

KM100. 岛屿的最大面积

题目链接:KM100. 岛屿的最大面积
在广度搜索中累计相邻陆地组成岛屿的面积,再在外部对比每块岛屿的面积取最大面积

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>using namespace std;
int max_count = 0;
int dir[4][2] = {{0,  1}, //列+1,右移{1,  0}, //行+1,下移{-1, 0},//行-1,上移{0,  -1} //列-1,左移
};void bfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y,int& count) {queue<pair<int, int>> que;que.push({x, y});visited[x][y] = true;count++;while (!que.empty()) {pair<int, int> cur = que.front();que.pop();for (int i = 0; i < 4; i++) {int next_x = cur.first + dir[i][0];int next_y = cur.second + dir[i][1];if (next_x < 0 || next_x >= grid.size() || next_y < 0 || next_y >= grid[0].size())continue;if (grid[next_x][next_y] == 1 && !visited[next_x][next_y]) {visited[next_x][next_y] = true;que.push({next_x, next_y});count++;}}}
};int main() {int N, M;std::cin >> N >> M;vector<vector<int>> grid(N, vector<int>(M, 0));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(N, vector<bool>(M, false));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (!visited[i][j] && grid[i][j] == 1) {int count = 0;bfs(grid, visited, i, j,count);max_count = max(max_count,count);}}}std::cout << max_count << std::endl;return 0;
};

相关文章:

代码随想录算法训练营第六十五天|KM99. 岛屿数量——深搜、KM99. 岛屿数量——广搜、KM100. 岛屿的最大面积

代码随想录算法训练营第六十五天 KM99. 岛屿数量——深搜 题目链接&#xff1a;KM99. 岛屿数量 使用递归深度搜索&#xff0c;将每次遇到的岛屿上下左右记录为已经到过&#xff0c;如果遇到没到过的说明它上下左右不是之间遍历过的岛屿&#xff0c;结果计数1。最后统计计数即…...

Lua 面向对象编程

Lua 面向对象编程 Lua 是一种轻量级的编程语言,通常用于嵌入应用程序中,提供灵活的扩展和定制功能。尽管 Lua 本身是一种过程式语言,但它提供了强大的元机制,允许开发者实现面向对象的编程范式。本文将探讨 Lua 中的面向对象编程(OOP)概念、实现方式以及最佳实践。 面向…...

AI赋能前端:你的Chrome 控制台需要AI(爱)

像会永生那样去学习,像明天就要死亡那样去生活。——圣雄甘地 大家好,我是柒八九。一个专注于前端开发技术/Rust及AI应用知识分享的Coder 此篇文章所涉及到的技术有 AI(Gemini)ChromeDevTool🪜魔法接码平台因为,行文字数所限,有些概念可能会一带而过亦或者提供对应的学习…...

代码随想录-Day38

509. 斐波那契数 斐波那契数 &#xff08;通常用 F(n) 表示&#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始&#xff0c;后面的每一项数字都是前面两项数字的和。也就是&#xff1a; F(0) 0&#xff0c;F(1) 1 F(n) F(n - 1) F(n - 2)&#xff0c;其中 …...

CSS阴影优化气泡框样式

<body> <div class"pop">气泡框</div> </body>body{display: flex;justify-content: center;align-items: center;height: 100% } .pop{display: flex;justify-content: center;align-items: center;background: #409eff;width: 150px;heigh…...

强化安全新篇章:韶关石油化工可燃气体报警器年检解析

韶关&#xff0c;这座位于广东省北部的城市&#xff0c;近年来在石油化工行业取得了显著的发展。 随着一批批大型石化企业的进驻和投产&#xff0c;韶关不仅成为了区域性的石化产业基地&#xff0c;也为地方经济带来了强劲的增长动力。 然而&#xff0c;随着石化产业的快速发…...

Centos7 Docker部署PgSQL

拉取镜像 docker pull postgres:14.7运行容器 docker run --restartalways --nethost --shm-size"2g" --name pgsql -v /home/postgresql/data/pgdata:/var/lib/postgresql/data -v /etc/localtime:/etc/localtime -e POSTGRES_PASSWORDtest2023 -d postgres:14…...

LeetCode:经典题之21、24 题解及延伸

系列目录 88.合并两个有序数组 52.螺旋数组 567.字符串的排列 643.子数组最大平均数 150.逆波兰表达式 61.旋转链表 160.相交链表 83.删除排序链表中的重复元素 389.找不同 1491.去掉最低工资和最高工资后的工资平均值 896.单调序列 206.反转链表 92.反转链表II 141.环形链表 …...

【C++11】initializer_list详解!

一、什么是initializer_list? nitializer_list 是一种C11新的类型特性&#xff0c;它允许我们以统一的方式初始化对象。它是一个代表数组的轻量级包装器&#xff0c;通常用于构造函数和函数参数中&#xff0c;以允许传递一个初始化元素列表。 initializer_list也是一种模板类…...

如何在Java中处理UnsupportedOperationException异常?

如何在Java中处理UnsupportedOperationException异常&#xff1f; 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01; 在Java编程中&#xff0c;我们经常会遇到各…...

WPS没保存关闭了怎么恢复数据?4个方法(更新版)

想象一下&#xff0c;你正在用WPS奋笔疾书&#xff0c;灵感如泉水般涌出&#xff0c;突然间&#xff0c;电脑却跟你开了个玩笑——啪地一下&#xff0c;文档未保存就关闭了&#xff01;是不是感觉像是被泼了一盆冷水&#xff0c;所有的热情瞬间熄灭&#xff1f;别急&#xff0c…...

elementplus el-table(行列互换)转置

Element Plus v2.4.0, repl v3.4.0 <template> <div><el-table :data"tableData" style"width: 100%"><el-table-column prop"name" label"名字" width"180" /><el-table-column prop"wei…...

Gradle 核心之 Task

一、前言 只有 Task 才可以在 Gradle 的执行阶段去执行&#xff08;其实质是执行的 Task 中的一系列 Action&#xff09;&#xff0c;所以 Task 的重要性不言而喻。 二、Task 2.1 Task 定义与配置 Task 的定义方式有如下两种&#xff1a; Task 的配置方式也有如下两种&#xf…...

【React 】折叠面板,点击展开时再请求数据

需求背景&#xff1a;使用折叠面板的形式展示数据&#xff0c;面板内部数据需要在打开时请求接口获取。 遇到问题&#xff1a;最开始使用Antd 的折叠面板组件&#xff0c;它对于数据直接渲染是没问题的&#xff0c;但是不好满足打开面板时再动态加载数据的需求&#xff0c;于是…...

c++学习 文件操作,模板

文件操作 #include<iostream> #include<string> #include<fstream> using namespace std; //文本操作 //程序运行时产生的数据都属于临时数据&#xff0c;程序一旦运行结束都会被释放 //通过文件可以数据持久化 //c中对文件操作包含头文件<fstream> /…...

开源与在线 M3U8 Downloader 项目介绍及使用指南

M3U8 是一种用于播放列表格式的文件类型&#xff0c;广泛应用于流媒体服务中&#xff0c;特别是 HLS&#xff08;HTTP Live Streaming&#xff09;协议。它包含了一系列的 TS&#xff08;Transport Stream&#xff09;视频片段地址&#xff0c;使得视频能够分段加载&#xff0c…...

正则表达式与文本处理器

正则表达式 基础正大表达式 查看特定字符 grep grep-n the test.txt grep-in the test.txt-n 显示行号 -i 不区分大小写 -v 反转查找 [] &#xff1a;中括号里可以写元素&#xff0c;内容符合任意元素&#xff0c;就会过滤出来 ^ :写在中括号里&#xff0c;代表取反。以^开头&…...

RedisTemplate方法一览表

数据类型RedisTemplate 方法Redis命令解释应用场景stringopsForValue().set(key, value)SET设置存储在指定 key 下的值存储简单数据&#xff0c;如用户的设置、配置项opsForValue().get(key)GET获取存储在指定 key 下的值读取存储的数据&#xff0c;如用户信息、配置参数opsFor…...

个人对devops的一点见解

DevOps 是一种将开发&#xff08;Development&#xff09;和运维&#xff08;Operations&#xff09;相结合的理念和实践方法。 它强调打破开发团队和运维团队之间的传统壁垒&#xff0c;促进两个团队之间更紧密的协作和沟通&#xff0c;以实现更高效、更快速、更可靠的软件交付…...

HarmonyOS鸿蒙应用开发基础知识

参考 HarmonyOS鸿蒙应用开发 (二、应用程序包结构理解及Ability的跳转&#xff0c;与Android的对比)_hap(harmonyos ability package)包的开发-CSDN博客 HarmonyOS NEXT下一代编程语言仓颉介绍及入门-CSDN博客...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...