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

代码随想录算法训练营 | 图论 | 孤岛总面积、沉没孤岛

101. 孤岛的总面积//思路大概是先计算面积,然后如果有接触路面就返回false。可能稍微多余算了太多无用面积。

#include<bits/stdc++.h>
using namespace std;
void sum(vector<vector<bool>>& finded,const vector<vector<int>>& graph,int a,int b,int& result,bool& Ifisland){if(a<0||b<0||a>graph.size()-1||b>graph[0].size()-1) return;else if(finded[a][b]==true) return;else if(graph[a][b]==0){finded[a][b]=true;return;}else {finded[a][b]=true;result++;if(a==0||b==0||a==graph.size()-1||b==graph[0].size()-1) Ifisland=false;sum(finded,graph,a+1,b,result,Ifisland);sum(finded,graph,a,b+1,result,Ifisland);sum(finded,graph,a-1,b,result,Ifisland);sum(finded,graph,a,b-1,result,Ifisland);}return;
}
int main(){int n,m;cin>>n>>m;vector<vector<int>> graph(n,vector<int> (m));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>graph[i][j];}}int sumcount=0;vector<vector<bool>> finded(n,vector<bool> (m));for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(graph[i][j]==1){bool Ifisland=true;int result=0;sum(finded,graph,i,j,result,Ifisland);if(Ifisland) sumcount+=result;} }}cout<<sumcount<<endl;    
}

102. 沉没孤岛//思路大致是,先遍历边框的,然后递归把连着的陆地都扫过,最后把没扫过的且为陆地的改为0。最后按题目的要求输出。

#include<bits/stdc++.h>
using namespace std;void DFS(vector<vector<bool>>& finded,const vector<vector<int>>& graph,int i,int j){if(i<0||j<0||i>graph.size()-1||j>graph[0].size()-1) return;else if(finded[i][j]) return;else if(graph[i][j]==0) {finded[i][j]=true;return;}else{finded[i][j]=true;DFS(finded,graph,i+1,j);DFS(finded,graph,i,j+1);DFS(finded,graph,i-1,j);DFS(finded,graph,i,j-1);}
}int main(){int n,m;cin>>n>>m;vector<vector<int>> graph(n,vector<int> (m));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>graph[i][j];}}vector<vector<bool>> finded(n,vector<bool> (m,false));    for(int i=0;i<n;i++){if(graph[i][0]==1&&!finded[i][0]) DFS(finded,graph,i,0);if(graph[i][m-1]==1&&!finded[i][m-1]) DFS(finded,graph,i,m-1);}  for(int j=0;j<m;j++){if(graph[0][j]==1&&!finded[0][j]) DFS(finded,graph,0,j);if(graph[n-1][j]==1&&!finded[n-1][j]) DFS(finded,graph,n-1,j);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(graph[i][j]==1&&!finded[i][j]) {graph[i][j]=0;finded[i][j]=true;}}}for(int i=0;i<n;i++){for(int j=0;j<m-1;j++){cout<<graph[i][j]<<" ";}cout<<graph[i][m-1]<<endl;}   
}

相关文章:

代码随想录算法训练营 | 图论 | 孤岛总面积、沉没孤岛

101. 孤岛的总面积//思路大概是先计算面积&#xff0c;然后如果有接触路面就返回false。可能稍微多余算了太多无用面积。 #include<bits/stdc.h> using namespace std; void sum(vector<vector<bool>>& finded,const vector<vector<int>>&a…...

迷你世界脚本出生点接口:Spawnport

出生点接口&#xff1a;Spawnport 彼得兔 更新时间: 2023-04-26 10:19:56 具体函数名及描述如下: 序号 函数名 函数描述 1 getSpawnPoint(...) 获取默认出生点 2 setSpawnPoint(...) 设置出生点位置 3 getChunkValidSpawnPos(...) 获取区块有效刷新点…...

双链路提升网络传输的可靠性扩展可用带宽

为了提升网络传输的可靠性或增加网络可用带宽&#xff0c; 通常使用双链路冗余备份或者双链路聚合的方式。 本文介绍几种双链路网络通信的案例。 5GWiFi冗余传输 双Socket绑定不同网络接口&#xff1a;通过Android的ConnectivityManager绑定5G蜂窝网络和WiFi的Socket连接&…...

Pytest测试用例执行跳过的3种方式

文章目录 1.前言2.使用 pytest.mark.skip 标记无条件跳过3.使用 pytest.mark.skipif 标记根据条件跳过4. 执行pytest.skip()方法跳过测试用例 1.前言 在实际场景中&#xff0c;我们可能某条测试用例没写完&#xff0c;代码执行时会报错&#xff0c;或者是在一些条件下不让某些…...

【蓝桥杯】每天一题,理解逻辑(3/90)【Leetcode 快乐数】

闲话系列&#xff1a;每日一题&#xff0c;秃头有我&#xff0c;Hello&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;,我是IF‘Maxue&#xff0c;欢迎大佬们来参观我写的蓝桥杯系列&#xff0c;我好久没有更新博客了&#xff0c;因为up猪我寒假用自己的劳动换了…...

深度学习Save Best、Early Stop

一、Save Best 今天的大模型&#xff0c;在训练过程中可能会终止&#xff0c;但是模型其实是可以接着练的&#xff0c;假设GPU挂了&#xff0c;可以接着训练&#xff0c;在原有的权重上&#xff0c;训练其实就是更新w&#xff0c;如果前面对w进行了存档&#xff0c;那么可以从…...

数据库与存储优化

一、MySQL深度优化 索引优化 B树索引结构 结构特点&#xff1a; 平衡多路搜索树&#xff0c;所有数据存储在叶子节点&#xff0c;非叶子节点仅存键值和指针。叶子节点通过双向链表连接&#xff0c;支持范围查询高效遍历。 优势&#xff1a; 减少磁盘IO&#xff08;高扇出&#…...

Android15请求动态申请存储权限完整示例

效果: 1.修改AndroidManifest.xml增加如下内容: <uses-permission android:name="android.permission.MANAGE_EXTERNAL_STORAGE" /><uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE" /><uses-perm...

C/C++蓝桥杯算法真题打卡(Day3)

一、P8598 [蓝桥杯 2013 省 AB] 错误票据 - 洛谷 算法代码&#xff1a; #include<bits/stdc.h> using namespace std;int main() {int N;cin >> N; // 读取数据行数unordered_map<int, int> idCount; // 用于统计每个ID出现的次数vector<int> ids; …...

【数据结构与算法】Java描述:第二节:LinkedList 链表

一、链表的概念与结构 1.1 概念&#xff1a; 通俗的来说&#xff0c;链表是由一个个结点连接起来的就叫链表。 1.2 结构&#xff1a; 链表存储的数据 在 物理上是不一定连续的&#xff0c;它是由前面链接后面&#xff0c;一个个连起来的。 二、Java底层的 LinkedList 2.1…...

LLM run

lmstudio lmstudio ollama ollama N 卡使用自带UI gpu加速推理 ,选择满足条件的&#xff0c; ds模型选择列表 https://ollama.com/library/deepseek-r1 a卡当前支持的显卡型号 I卡 gpu加速配置 2025.3 intel Official project optimization https://www.modelscope.cn/m…...

k8s面试题总结(十)

1.为什么HDFS不适合存储小文件&#xff1f; 元数据存储在NameNode内存中&#xff0c;一个节点的内存是有限的。存储大量的小文件会消耗过多的寻道时间 同等大小一个大文件的访问速度一定比多个小文件访问速度快 3.NameNode存储block的数量是有限的 比如你一个block元数据需要消…...

android中activity1和activity2中接收定时消息

android中activity1和activity2中接收定时消息 业务类 import java.util.Timer; import java.util.TimerTask;public class MyAnager {private MyAnager() {}private static MyAnager instance;//回调接口onRecvTaskpublic interface OnMsgListener {void onRecvTask(String a…...

Non-Homophilic Graph Pre-Training and Prompt Learning

Non-Homophilic Graph Pre-Training and Prompt Learning KDD25 ​#paper/⭐#​ 目的&#xff1a;对异配图进行prompt ‍ ​​ 方法 邻居节点的综合嵌入 s v 1 ∣ V ( S v ) ∣ ∑ u ∈ V ( S v ) h u ⋅ s i m ( h u , h v ) , \mathbf{s}_{v}\frac{1}{|V(S_{v})|}\su…...

Ollama 框架本地部署教程:开源定制,为AI 项目打造专属解决方案!

Ollama 是一款开源的本地大语言模型&#xff08;LLM&#xff09;运行框架&#xff0c;用于管理和运行语言模型。具有以下核心特点&#xff1a; 开源可定制&#xff1a;采用 MIT 开源协议&#xff0c;开发者能自由使用、阅读源码并定制&#xff0c;可根据自身需求进行功能扩展和…...

unittest框架 核心知识的系统复习及与pytest的对比

1. unittest 介绍 是什么&#xff1a;Python 标准库自带的单元测试框架&#xff0c;遵循 xUnit 架构&#xff08;类似Java的JUnit&#xff09;。 核心概念&#xff1a; TestCase&#xff1a;测试用例的基类&#xff0c;所有测试类需继承它。 TestSuite&#xff1a;测试套件&a…...

vue面试宝典之二

39.vue2和vue3中源码是如何解析模版的 new vue&#xff08;&#xff09;的时候实例化了类之后根据传进去的option进行模版的类型div还是text还是啥进行匹配&#xff0c;同时拿到节点的值进行绑定&#xff0c;比如正则匹配{{}}将匹配到的变量拿去跟option中的data查找到具体的值…...

ESLint 深度解析:原理、规则与插件开发实践

在前端开发的复杂生态中&#xff0c;保障代码质量与规范性是构建稳健、可维护项目的基石。ESLint 作为一款强大的代码检查工具&#xff0c;其默认规则与插件能满足多数常见需求&#xff0c;但面对特定团队规范或项目独特要求&#xff0c;自定义 ESLint 插件便成为有力的扩展手段…...

洛谷P1091

题目如下 思路 谢谢观看...

随机树算法 自动驾驶汽车的路径规划 静态障碍物(Matlab)

随着自动驾驶技术的蓬勃发展&#xff0c;安全、高效的路径规划成为核心挑战之一。快速探索随机树&#xff08;RRT&#xff09;算法作为一种强大的路径搜索策略&#xff0c;为自动驾驶汽车在复杂环境下绕过静态障碍物规划合理路径提供了有效解决方案。 RRT 算法基于随机采样思想…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...