代码随想录算法训练营 | 图论 | 孤岛总面积、沉没孤岛
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. 孤岛的总面积//思路大概是先计算面积,然后如果有接触路面就返回false。可能稍微多余算了太多无用面积。 #include<bits/stdc.h> using namespace std; void sum(vector<vector<bool>>& finded,const vector<vector<int>>&a…...
迷你世界脚本出生点接口:Spawnport
出生点接口:Spawnport 彼得兔 更新时间: 2023-04-26 10:19:56 具体函数名及描述如下: 序号 函数名 函数描述 1 getSpawnPoint(...) 获取默认出生点 2 setSpawnPoint(...) 设置出生点位置 3 getChunkValidSpawnPos(...) 获取区块有效刷新点…...
双链路提升网络传输的可靠性扩展可用带宽
为了提升网络传输的可靠性或增加网络可用带宽, 通常使用双链路冗余备份或者双链路聚合的方式。 本文介绍几种双链路网络通信的案例。 5GWiFi冗余传输 双Socket绑定不同网络接口:通过Android的ConnectivityManager绑定5G蜂窝网络和WiFi的Socket连接&…...
Pytest测试用例执行跳过的3种方式
文章目录 1.前言2.使用 pytest.mark.skip 标记无条件跳过3.使用 pytest.mark.skipif 标记根据条件跳过4. 执行pytest.skip()方法跳过测试用例 1.前言 在实际场景中,我们可能某条测试用例没写完,代码执行时会报错,或者是在一些条件下不让某些…...
【蓝桥杯】每天一题,理解逻辑(3/90)【Leetcode 快乐数】
闲话系列:每日一题,秃头有我,Hello!!!!!,我是IF‘Maxue,欢迎大佬们来参观我写的蓝桥杯系列,我好久没有更新博客了,因为up猪我寒假用自己的劳动换了…...
深度学习Save Best、Early Stop
一、Save Best 今天的大模型,在训练过程中可能会终止,但是模型其实是可以接着练的,假设GPU挂了,可以接着训练,在原有的权重上,训练其实就是更新w,如果前面对w进行了存档,那么可以从…...
数据库与存储优化
一、MySQL深度优化 索引优化 B树索引结构 结构特点: 平衡多路搜索树,所有数据存储在叶子节点,非叶子节点仅存键值和指针。叶子节点通过双向链表连接,支持范围查询高效遍历。 优势: 减少磁盘IO(高扇出&#…...
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] 错误票据 - 洛谷 算法代码: #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 概念: 通俗的来说,链表是由一个个结点连接起来的就叫链表。 1.2 结构: 链表存储的数据 在 物理上是不一定连续的,它是由前面链接后面,一个个连起来的。 二、Java底层的 LinkedList 2.1…...
LLM run
lmstudio lmstudio ollama ollama N 卡使用自带UI gpu加速推理 ,选择满足条件的, ds模型选择列表 https://ollama.com/library/deepseek-r1 a卡当前支持的显卡型号 I卡 gpu加速配置 2025.3 intel Official project optimization https://www.modelscope.cn/m…...
k8s面试题总结(十)
1.为什么HDFS不适合存储小文件? 元数据存储在NameNode内存中,一个节点的内存是有限的。存储大量的小文件会消耗过多的寻道时间 同等大小一个大文件的访问速度一定比多个小文件访问速度快 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/⭐# 目的:对异配图进行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 是一款开源的本地大语言模型(LLM)运行框架,用于管理和运行语言模型。具有以下核心特点: 开源可定制:采用 MIT 开源协议,开发者能自由使用、阅读源码并定制,可根据自身需求进行功能扩展和…...
unittest框架 核心知识的系统复习及与pytest的对比
1. unittest 介绍 是什么:Python 标准库自带的单元测试框架,遵循 xUnit 架构(类似Java的JUnit)。 核心概念: TestCase:测试用例的基类,所有测试类需继承它。 TestSuite:测试套件&a…...
vue面试宝典之二
39.vue2和vue3中源码是如何解析模版的 new vue()的时候实例化了类之后根据传进去的option进行模版的类型div还是text还是啥进行匹配,同时拿到节点的值进行绑定,比如正则匹配{{}}将匹配到的变量拿去跟option中的data查找到具体的值…...
ESLint 深度解析:原理、规则与插件开发实践
在前端开发的复杂生态中,保障代码质量与规范性是构建稳健、可维护项目的基石。ESLint 作为一款强大的代码检查工具,其默认规则与插件能满足多数常见需求,但面对特定团队规范或项目独特要求,自定义 ESLint 插件便成为有力的扩展手段…...
洛谷P1091
题目如下 思路 谢谢观看...
随机树算法 自动驾驶汽车的路径规划 静态障碍物(Matlab)
随着自动驾驶技术的蓬勃发展,安全、高效的路径规划成为核心挑战之一。快速探索随机树(RRT)算法作为一种强大的路径搜索策略,为自动驾驶汽车在复杂环境下绕过静态障碍物规划合理路径提供了有效解决方案。 RRT 算法基于随机采样思想…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
Ubuntu系统多网卡多相机IP设置方法
目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机,交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息,系统版本:Ubuntu22.04.5 LTS;内核版本…...
