当前位置: 首页 > 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博客...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...