代码随想录打卡第五十三天

代码随想录–图论部分

day 53 图论第三天


文章目录

  • 代码随想录--图论部分
  • 一、卡码网101--孤岛的总面积
  • 二、卡码网102--沉没孤岛
  • 三、卡码网103--水流问题
  • 四、卡码网104--建造最大岛屿


一、卡码网101–孤岛的总面积

代码随想录题目链接:代码随想录

给定一个由 1(陆地)和 0(水)组成的矩阵,岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域,且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要计算所有孤岛的总面积,岛屿面积的计算方式为组成岛屿的陆地的总数。

将那些与边界相接触的岛全部变成0,那么剩下的就是孤立的岛屿,遍历相加即可

所以遍历顺序也有说法,不再是从左到右从上到下,而是只搜索边界

当边界有1,那么说明这里有个岛屿接触边界了,要把这整个岛屿删了

代码如下:

#include <iostream>
#include <vector>using namespace std;
void dfs(vector<vector<int>> & graph, int i, int j)
{int rows = graph.size();int cols = graph[0].size();if(i < 0 || j < 0 || i >= rows || j >= cols || !graph[i][j]) return;graph[i][j] = 0;dfs(graph, i - 1, j);dfs(graph, i + 1, j);dfs(graph, i, j - 1);dfs(graph, i, j + 1);}int main()
{int n,m;cin >> n >> m;vector<vector<int>> graph(n, vector<int>(m, 0));for(int i = 0; i < n; i ++)for(int j = 0; j < m; j ++)cin >> graph[i][j];for(int i = 0; i < n; i ++){if(graph[i][0]) dfs(graph, i, 0);if(graph[i][m - 1]) dfs(graph, i, m - 1);}for(int i = 0; i < m; i ++){if(graph[0][i]) dfs(graph, 0, i);if(graph[n - 1][i]) dfs(graph, n - 1, i);}int result = 0;for(int i = 0; i < n; i ++)for(int j = 0; j < m; j ++)if(graph[i][j]) result++;cout << result << endl;}

二、卡码网102–沉没孤岛

代码随想录题目链接:代码随想录

给定一个由 1(陆地)和 0(水)组成的矩阵,岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域,且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要将所有孤岛“沉没”,即将孤岛中的所有陆地单元格(1)转变为水域单元格(0)。

和上题一样,只需要在边界搜索时记录下来非孤立岛屿的位置

后续输出即可

代码如下:

#include <iostream>
#include <vector>using namespace std;vector<vector<int>> result;
void dfs(vector<vector<int>> & graph, int i, int j)
{int rows = graph.size();int cols = graph[0].size();if(i < 0 || j < 0 || i >= rows || j >= cols || !graph[i][j]) return;graph[i][j] = 0;result.push_back({i, j});dfs(graph, i - 1, j);dfs(graph, i + 1, j);dfs(graph, i, j - 1);dfs(graph, i, j + 1);}int main()
{int n,m;cin >> n >> m;vector<vector<int>> graph(n, vector<int>(m, 0));for(int i = 0; i < n; i ++)for(int j = 0; j < m; j ++)cin >> graph[i][j];for(int i = 0; i < n; i ++){if(graph[i][0] == 1) dfs(graph, i, 0);if(graph[i][m - 1] == 1) dfs(graph, i, m - 1);}for(int i = 0; i < m; i ++){if(graph[0][i] == 1) dfs(graph, 0, i);if(graph[n - 1][i] == 1) dfs(graph, n - 1, i);}vector<vector<int>> graph_out(n, vector<int>(m, 0));for(auto ele : result){graph_out[ele[0]][ele[1]] = 1;}for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++){cout << graph_out[i][j] << " ";}        cout << endl;}}

三、卡码网103–水流问题

代码随想录题目链接:代码随想录

现有一个 N × M 的矩阵,每个单元格包含一个数值,这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界,而矩阵的右边界和下边界被视为第二组边界。

矩阵模拟了一个地形,当雨水落在上面时,水会根据地形的倾斜向低处流动,但只能从较高或等高的地点流向较低或等高并且相邻(上下左右方向)的地点。我们的目标是确定那些单元格,从这些单元格出发的水可以达到第一组边界和第二组边界。

也就是需要找到某些单元格,按照元素递减的顺序能够到达左/上边界以及右/下边界

在这里插入图片描述

则可以从两个边界分别开始遍历,记录每个节点能够到达的地点

保存两个边界分别能遍历到的节点,重叠的部分就是需要输出的结果

代码如下:

#include <iostream>
#include <vector>using namespace std;vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};void dfs(vector<vector<int>> & graph, vector<vector<int>> & border, int i, int j)
{if(border[i][j]) return;border[i][j] = 1;int rows = graph.size();int cols = graph[0].size();for(auto ele : directions){int x = i + ele.first;int y = j + ele.second;if(x < 0 || y < 0 || x >= rows || y >= cols) continue;if(graph[i][j] <= graph[x][y]) dfs(graph, border, x, y);}}
int main()
{int n, m;cin >> n >> m;vector<vector<int>> graph(n, vector<int>(m, 0));for(int i = 0;i < n; ++ i)for(int j = 0; j < m; ++j)cin >> graph[i][j];vector<vector<int>> first(n, vector<int>(m, 0));vector<vector<int>> second(n, vector<int>(m, 0));for(int i = 0; i < n ; ++ i){dfs(graph, first, i, 0);dfs(graph, second, i, m - 1);}for(int i = 0; i < m ; ++ i){dfs(graph, first, 0, i);dfs(graph, second, n - 1, i);}for(int i = 0;i < n; ++ i)for(int j = 0; j < m; ++j)if(first[i][j] && second[i][j]) cout << i << " "<< j << endl; return 0;
}

四、卡码网104–建造最大岛屿

代码随想录题目链接:代码随想录

给定一个由 1(陆地)和 0(水)组成的矩阵,你最多可以将矩阵中的一格水变为一块陆地,在执行了此操作之后,矩阵中最大的岛屿面积是多少。

岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿是被水包围,并且通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。

暴力法就是遍历,每次改成0后就算一次最大岛屿面积,取遍历结束的最大值,自然是超时

实际上可以记录每个岛的大小,再遍历每个0点,计算如果它周围链接岛屿的面积和

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int n, m;
int count;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int mark) {if (visited[x][y] || grid[x][y] == 0) return; // 终止条件:访问过的节点 或者 遇到海水visited[x][y] = true; // 标记访问过grid[x][y] = mark; // 给陆地标记新标签count++;for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;  // 越界了,直接跳过dfs(grid, visited, nextx, nexty, mark);}
}int main() {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)); // 标记访问过的点unordered_map<int ,int> gridNum;int mark = 2; // 记录每个岛屿的编号bool isAllGrid = true; // 标记是否整个地图都是陆地for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 0) isAllGrid = false;if (!visited[i][j] && grid[i][j] == 1) {count = 0;dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 truegridNum[mark] = count; // 记录每一个岛屿的面积mark++; // 记录下一个岛屿编号}}}if (isAllGrid) {cout << n * m << endl; return 0;}int result = 0; unordered_set<int> visitedGrid; for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {count = 1; visitedGrid.clear(); if (grid[i][j] == 0) {for (int k = 0; k < 4; k++) {int neari = i + dir[k][1]; int nearj = j + dir[k][0];if (neari < 0 || neari >= n || nearj < 0 || nearj >= m) continue;if (visitedGrid.count(grid[neari][nearj])) continue; count += gridNum[grid[neari][nearj]];visitedGrid.insert(grid[neari][nearj]); }}result = max(result, count);}}cout << result << endl;}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/397565.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

绘图仪 -- Web前端开发和Canvas绘图

Canvas绘图介绍 Canvas绘图是HTML5中引入的一个非常强大的特性&#xff0c;它允许开发者使用JavaScript在网页上绘制图形、图表、动画等。<canvas>元素提供了一个通过JavaScript和Canvas API进行绘图的环境。 创建绘图仪对象 // 定义一个名为 XYPlotter 的函数&#x…

Mapboxgl 实现弧线功能

更多精彩内容尽在 dt.sim3d.cn &#xff0c;关注公众号【sky的数孪技术】&#xff0c;技术交流、源码下载请添加VX&#xff1a;digital_twin123 代码如下&#xff1a; const mapCenter [-0.5, 51.8];// please use your own token! const map new mapboxgl.Map({container: …

怎样才算精通 Excel?

最强AI视频生成&#xff1a;小说文案智能分镜智能识别角色和场景批量Ai绘图自动配音添加音乐一键合成视频百万播放量https://aitools.jurilu.com/ 高赞回答很系统&#xff0c;但普通人这么学&#xff0c;没等精通先学废了&#xff01; 4年前&#xff0c;我为了学数据分析&#…

iOS Object-C 创建类别(Category) 与使用

有时候使用系统给出类或者第三方的类,但是呢它们自带的属性和方法又太少,不够我们的业务使用,这时候就需要给“系统的类或者第三方类”创建一个类别(Category),把自己的想添加的属性和方法写进来. Category模式用于向已经存在的类添加方法从而达到扩展已有类的目的 一:创建Ca…

继承(二)

隐藏/重定义&#xff1a;子类和父类有同名的成员&#xff0c;子类成员隐藏了父类的成员。 重载&#xff1a;同一个作用域&#xff0c;重载了参数。 &#xff08;在实际中最好不要定义同名函数&#xff09; 子类对象不能初始化父类对象&#xff0c;用父类成员初始化子类成员。…

开关电源之结构分析

如有技术问题及技术需求请加作者微信! 开关电源之结构分析 1、开关电源的结构 常用开关电源,主要是为电子设备提供直流电源供电。电子设备所需要的直流电压,范围一般都在几伏到十几伏,而交流市电电源供给的电压为220V(110V),频率为50Hz(60Hz)。开关电源的作用就是把一…

【Unity】线性代数基础:矩阵、矩阵乘法、转置矩阵、逆矩阵、正交矩阵等

文章目录 矩阵&#xff08;Matrix&#xff09;矩阵能干啥&#xff1f;矩阵基本运算矩阵加减法矩阵和标量的乘法矩阵和矩阵的乘法矩阵的转置矩阵相等 特殊的矩阵方块矩阵对称矩阵对角元素&#xff08;Diagonal Elements&#xff09;对角矩阵&#xff08;Diagonal Matrix&#xf…

C语言-函数

一、函数的概念 其实在C语⾔也引⼊函数&#xff08;function&#xff09;的概念&#xff0c;有些翻译为&#xff1a;⼦程序&#xff0c;⼦程序这种翻译更加准确⼀些。C语⾔中的函数就是⼀个完成某项特定的任务的⼀⼩段代码。这段代码是有特殊的写法和调⽤⽅法的。C语⾔的程序其…

hs_err_pid.log分析

hs_err_pid.log 文件是 Java 虚拟机&#xff08;JVM&#xff09;在遇到致命错误&#xff08;如崩溃或内部错误&#xff09;时生成的错误日志文件。这个文件包含了关于崩溃的详细信息&#xff0c;可以帮助开发者或系统管理员诊断和解决问题。 hs_err_pid.log文件位置和命名 文…

基于springboot3实现单点登录(二):认证服务端搭建

前言 上文我们介绍了oauth2.0的相关理论和流程&#xff0c;本文我们继续实现。 Oauth2协议中有个很重要的概念&#xff0c;叫做”端点“&#xff0c; 以下整理了一些常用的端点及其参考访问路径及使用场景的信息&#xff0c;供参考。 这些端点在oauth2.0协议的整个生命周期…

python自动化笔记:操作mysql数据库

操作mysql数据库常见方法 1、第三方库&#xff1a;pymysql1.1、安装pymysql1.2、连接数据库1.3、连接指定数据库1.4 创建数据库、创建表1.5、表中插入数据1.6、批量插入数据1.7、获取查询结果数据1.8、防sql注入&#xff0c;sql语句中一般用占位符传值 2、标准库 &#xff1a;m…

【《Kafka 入门指南:从零基础到精通》】

前言&#xff1a; &#x1f49e;&#x1f49e;大家好&#xff0c;我是书生♡&#xff0c;本阶段和大家一起分享和探索KAFKA&#xff0c;本篇文章主要讲述了&#xff1a;消息队列的基础知识&#xff0c;KAFKA消息队列等等。欢迎大家一起探索讨论&#xff01;&#xff01;&#x…

rocketMQ5.0事务消息实战

事务消息逻辑 docker部署容器&#xff0c;并且创建消息 dd首先我们来docker 部署rocketMQ与rocketMQDashBoard docker ps查看rocketMQ 容器名称 docker ps 进入容器内部 docker exec -it rmqnamesrv /bin/bash 创建事务消息 MeessageType: TRANSACTION sh mqadmin upda…

Linux驱动.之I2C,iic驱动层(二)

一、 Linux下IIC驱动架构 本篇只分析&#xff0c;一个整体框架。 1、首先说说&#xff0c;单片机&#xff0c;的i2c硬件接口图&#xff0c;一个i2c接口&#xff0c;通过sda和scl总线&#xff0c;外接了多个设备device&#xff0c;通过单片机&#xff0c;来控制i2c的信号发生&…

解锁数据“智能”背后的秘密

在这个被数据洪流包围的时代&#xff0c;每一秒都有无数的信息在生成、传递、分析。但你是否曾好奇&#xff0c;这些数据是如何从简单的数字、文字转化为推动社会进步、改变生活方式的“智能”力量的&#xff1f;今天&#xff0c;就让我们一起揭开数据“智能”背后的神秘面纱&a…

C语言文达学院班级管理系统-计算机毕业设计源码03499

摘 要 本文阐述了一个C语言文达学院班级管理系统的设计与实现过程。该系统充分利用ASP.NET的轻量级、灵活性和可扩展性&#xff0c;旨在为文达学院提供高效、便捷的班级管理系统。通过详细的需求分析、技术选型、系统设计、开发实现、测试与调试以及部署与上线等步骤&#xff0…

通过python管理mysql

打开防火墙端口&#xff1a; 使用 firewall-cmd 命令在防火墙的 public 区域中永久添加 TCP 端口 7500&#xff08;FRP 控制台面板端口&#xff09;、7000&#xff08;FRP 服务端端口&#xff09;以及端口范围 6000-6100&#xff08;一组客户端端口&#xff09;。这些端口是 FR…

Unity补完计划 之 动态控制TileMap

本文仅作笔记学习和分享&#xff0c;不用做任何商业用途 本文包括但不限于unity官方手册&#xff0c;unity唐老狮等教程知识&#xff0c;如有不足还请斧正 1.TileMap &TileBase Unity - Scripting API: Tilemap &#xff0c;看手册内容太多了故介绍几个常用的公共方法 首…

【凌鸥学园】电机电控课程学习,挑战自我!

电控达人集结号&#xff01;凌鸥学园精心打造的电机电控课程&#xff0c;现面向全体爱好者及专业人士免费开放&#xff01; 课程内容从基础原理到高级应用&#xff0c;全方位助力你快速掌握电机电控精髓&#xff0c;实现技能飞跃&#xff01; 挑战成功&#xff0c;双重奖励等…

12. 矩阵中的路径

comments: true difficulty: 中等 edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9812.%20%E7%9F%A9%E9%98%B5%E4%B8%AD%E7%9A%84%E8%B7%AF%E5%BE%84/README.md 面试题 12. 矩阵中的路径 题目描述 给定一个 m x n 二维字符网格 board…