当前位置: 首页 > 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 算法基于随机采样思想…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...