图论基础--孤岛系列
孤岛系列有:
孤岛总面积求解(用了dfs、bfs两种方法)和沉没孤岛(这里只写了dfs一种)
简单解释一下:
题目中孤岛的定义是与边缘没有任何接触的(也就是不和二维数组的最外圈连接),所以我们在这里求面积和沉没孤岛都是先把不是孤岛的剔除 ,然后剩下的就是孤岛,然后处理起来就简单多了,那么我们这里是怎么遍历不是孤岛的岛呢,很简单,与数组外圈的1相连的肯定就不是孤岛,所以我们直接从四个方向的边缘遍历将他们都处理掉。
其实都是dfs、bfs的模板题、基础题,都比较简单,这里贴出代码(太懒了,都写在了一个代码里...)
题目、题解链接:代码随想录
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class TheSquareOfIsolatedIsland {public static int ans=0;public static int[][] next={{1,0},{0,1},{-1,0},{0,-1}};// dfs遍历计算孤岛面积public static void dfs(int[][] grid,int x,int y){grid[x][y]=0;ans++;for(int i=0;i<4;i++){int nextX=x+next[i][0];int nextY=y+next[i][1];if(nextX<0||nextX>=grid.length||nextY<0||nextY>=grid[0].length||grid[nextX][nextY]==0) continue;dfs(grid,nextX,nextY);}}// bfs遍历计算孤岛面积public static void bfs(int[][] grid,int x,int y){Queue<int[]> queue=new LinkedList<>();queue.add(new int[] {x,y});grid[x][y]=0;ans++;while(!queue.isEmpty()){int[] theNext=queue.poll();int xx=theNext[0];int yy=theNext[1];for(int i=0;i<4;i++){int nextX=xx+next[i][0];int nextY=yy+next[i][1];if(nextX<0||nextX>=grid.length||nextY<0||nextY>=grid[0].length||grid[nextX][nextY]==0) continue;queue.add(new int[] {nextX,nextY});ans++;grid[nextX][nextY]=0;}}}// 沉没孤岛public static void dfs2(int[][] grid,int x,int y){grid[x][y]=-1;for(int i=0;i<4;i++){int nextX=x+next[i][0];int nextY=y+next[i][1];if(nextX<0||nextY<0||nextX>=grid.length||nextY>= grid[0].length) continue;if(grid[nextX][nextY]==0||grid[nextX][nextY]==-1) continue;dfs2(grid,nextX,nextY);}}public static void main(String[] args){Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();int m=scanner.nextInt();int[][] grid=new int[n][m];for(int i=0;i<n;i++){for(int j=0;j<m;j++){grid[i][j]=scanner.nextInt();}}scanner.close();for(int i=0;i<n;i++){if(grid[i][0]==1) dfs2(grid,i,0);if(grid[i][m-1]==1) dfs2(grid,i,m-1);}for(int j=0;j<m;j++){if(grid[0][j]==1) dfs2(grid,0,j);if(grid[n-1][j]==1) dfs2(grid,n-1,j);}ans=0;
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++){
// if(grid[i][j]==1) bfs(grid,i,j);
// }
// }System.out.println(ans);// 沉没孤岛输出操作for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1) grid[i][j]=1;if(grid[i][j]==-1) grid[i][j]=0;}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){System.out.print(grid[i][j]+" ");}System.out.println();}}
}
相关文章:
图论基础--孤岛系列
孤岛系列有: 孤岛总面积求解(用了dfs、bfs两种方法)和沉没孤岛(这里只写了dfs一种) 简单解释一下: 题目中孤岛的定义是与边缘没有任何接触的(也就是不和二维数组的最外圈连接)&…...
Docker学习—Docker的安装与使用
Docker安装 1.卸载旧版 首先如果系统中已经存在旧的Docker,则先卸载: yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine2.配置Docker的yum库 首先…...
HC-SR04超声波传感器详解(STM32)
HC-SR04是一款广泛使用的超声波传感器,它通过发射和接收超声波来测量距离。本文将详细介绍HC-SR04的工作原理、引脚描述、STM32的接线方式以及如何通过STM32控制HC-SR04来测量距离。 一、HC-SR04传感器介绍 HC-SR04超声波传感器的主要参数如下: 工作电…...
如何在BSV区块链上实现可验证AI
发表时间:2024年10月2日 nChain的顶尖专家们已经找到并成功测试了一种方法:通过区块链技术来验证AI(人工智能)系统的输出结果。这种方法可以确保AI模型既按照规范运行,避免严重错误,遵守诸如公平、透明…...
Python快速安装软件包到环境的方案
问题描述 直接在终端输入,显示安装numpy包要20分钟, pip install numpyxxx.whl解决方案 直接搜索pip install 后在终端显示的.whl文件,在pypi.org官网下载, 之后在终端进入下载目录,从.whl文件安装软件包即可 pip …...
npm入门教程17:准备发布的npm包
一、环境准备 安装Node.js和npm: 确保你的计算机上已安装Node.js和npm。可以通过运行node -v和npm -v命令来检查它们的版本。如果没有安装,可以从Node.js官方网站下载并安装最新版本。 注册npm账号: 访问npm官网,点击“Sign Up”…...
协程1 --- 发展历史
文章目录 一个编译器问题背景解决 协程为什么一开始没发展成一等公民?自顶向下、逐步求精(Top-down, stepwise refinement)线程的出现 协程的雄起IO密集型同步语义实现异步发展史 线程和协程的关系并发性调度方式资源占用 一个编译器问题 协…...
VBA10-处理Excel的动态数据区域
end获取数据边界 1、基本语法 1-1、示例: 2、配合row和column使用 2-1、示例1 2-2、示例2 此时,不管这个有数值的区域,怎么增加边界,对应的统计数据也会跟着变的!...
【git】使用记录
一、安装 参考:Git2.45.2下载安装记录(windows 11)_win11安装git-CSDN博客...
代码随想录算法训练营第三十八天|Day38 动态规划
322. 零钱兑换 视频讲解:https://www.bilibili.com/video/BV14K411R7yv https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html 思路 #define min(a, b) ((a) > (b) ? (b) : (a)) int coinChange(int* coins, int coinsSize, int amount…...
使用C++和libcurl库实现HTTP请求(GET、POST、文件上传)
在现代软件开发中,与外部API服务进行通信已成为常见需求。本文将展示如何使用C和libcurl库实现基本的HTTP请求,包括GET请求、POST请求(带JSON数据)以及包含文件上传的POST请求。 准备工作 首先,需要确保已安装libcur…...
makefile例子
$指代当前目标,就是Make命令当前构建的那个目标。比如,make foo的 $ 就指代foo。 $< 指代第一个前置条件。比如,规则为 t: p1 p2,那么$< 就指代p1。 $? 指代比目标更新的所有前置条件,之间以空格分隔。比如&a…...
用环形数组实现队列(多种高级方法,由浅入深)
同普通数组实现的队列相比,普通数组的头结点和尾节点都是固定的,在进行移除的时候如果移除了一个节点,后面所有节点都需要进行移除操作,需要的时间复杂度更高 在环形数组中,确定了头尾指针的环形数组很好地解决了这一…...
springboot框架使用RabbitMQ举例代码
以前分享过一个理论有兴趣的小伙伴可以看下 https://blog.csdn.net/Drug_/article/details/138164180 不多说 还是直接上代码 第一步:引入依赖 可以不指定版本 <!-- amqp --><dependency><groupId>org.springframework.boot</groupId…...
Java实现一个延时队列
文章目录 前言正文一、基本概念1.1 延时队列的特点1.2 常见的实现方式 二、Java原生的内存型延时队列2.1 定义延时元素DelayedElement2.2 定义延时队列管理器DelayedQueueManager2.3 消费元素2.4 调试2.5 调试结果2.6 精髓之 DelayQueue.poll() 三、基于Redisson的延时队列3.1 …...
为什么说vue是双向数据流
Vue.js 被称为 双向数据绑定(two-way data binding),是因为它支持数据在 视图(View) 和 模型(Model) 之间双向流动。这意味着,当 数据变化 时,视图会自动更新;…...
创造属于你的 Claude Prompt 和个性化 SVG 卡片|对李继刚老师提示词的浅浅解析与总结
❤️ 如果你也关注大模型与 AI 的发展现状,且对大模型应用开发非常感兴趣,我会快速跟你分享最新的感兴趣的 AI 应用和热点信息,也会不定期分享自己的想法和开源实例,欢迎关注我哦! 🥦 微信公众号ÿ…...
redis与本地缓存
本地缓存是将数据存储在应用程序所在的本地内存中的缓存方式。既然,已经有了 Redis 可以实现分布式缓存了,为什么还需要本地缓存呢?接下来,我们一起来看。 为什么需要本地缓存? 尽管已经有 Redis 缓存了,但…...
git撤销commit和add
撤销commit git reset --soft HEAD^撤销add git reset .查看状态 git status...
【361】基于springboot的招生宣传管理系统
摘 要 使用旧方法对招生宣传管理系统的信息进行系统化管理已经不再让人们信赖了,把现在的网络信息技术运用在招生宣传管理系统的管理上面可以解决许多信息管理上面的难题,比如处理数据时间很长,数据存在错误不能及时纠正等问题。这次开发的招…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
