腐烂的橘子BFS
题目: 腐烂的橘子
在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:
-
值 0 代表空单元格;
-
值 1 代表新鲜橘子;
-
值 2 代表腐烂的橘子。
每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1 。
解题思路:
这道题可以使用广度优先搜索(BFS)来解决。我们首先将所有初始状态为腐烂的橙子加入队列,然后进行广度优先搜索。在每一轮搜索中,我们从队列中取出腐烂的橙子,尝试向上下左右四个方向传播腐烂。如果某个方向上有新鲜橙子,我们将其变为腐烂橙子,并将其位置加入队列。重复这个过程直到队列为空,即所有可能的腐烂传播都完成。
代码:
public class OrangesRotting {int[][] xx = {{0, -1},{-1, 0}, {0, 1}, {1, 0}};/*** 计算腐烂的橙子数量。** @param grid 二维数组表示果园的状态,1 代表新鲜橙子,2 代表腐烂橙子,0 代表空格。* @return 如果所有新鲜橙子都腐烂了,返回腐烂过程需要的最小天数;如果无法全部腐烂,则返回 -1。*/public int orangesRotting(int[][] grid) {// 获取果园的行数和列数int m = grid.length, n = grid[0].length, res = 0;// 使用队列保存腐烂橙子的位置,以便进行广度优先搜索Queue<int[]> queue = new LinkedList<>();// 将所有初始状态为腐烂的橙子加入队列for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(grid[i][j] == 2) queue.offer(new int[]{i,j});}}// 广度优先搜索,直到队列为空while(!queue.isEmpty()){// 当前队列中的橙子数量int size = queue.size();// 标记当前是否有橙子腐烂boolean flag = false;// 遍历当前队列中的所有橙子for(int i = 0;i < size;i++){int[] d = queue.poll();int x = d[0], y = d[1];// 尝试从当前腐烂橙子的位置向四个方向传播腐烂for(int[] t : xx){int xx = x + t[0], yy = t[1] + y;// 跳过越界的橙子、已经是腐烂的橙子和空格if(xx < 0 || yy < 0 || xx == m || yy == n|| grid[xx][yy] == 0 || grid[xx][yy] == 2) continue;// 将新鲜橙子变为腐烂橙子,并将其位置加入队列,标记腐烂发生grid[xx][yy] = 2;flag = true;queue.offer(new int[]{xx,yy});}}// 如果本次有橙子腐烂,则结果加一if(flag) res++;}// 检查果园中是否还有新鲜橙子,有则返回 -1,表示无法全部腐烂for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(grid[i][j] == 1) return -1;}}return res;}
}
相关文章:

腐烂的橘子BFS
题目: 腐烂的橘子 在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一: 值 0 代表空单元格; 值 1 代表新鲜橘子; 值 2 代表腐烂的橘子。 每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子…...

什么是分库分表
读写分离主要应对的是数据库读并发,没有解决数据库存储问题。试想一下:如果 MySQL 一张表的数据量过大怎么办? 答案当然是分库分表 什么是分库? 分库 就是将数据库中的数据分散到不同的数据库上,可以垂直分库,也可…...
pytest并发执行用例方案
背景 开始做新项目的UI自动化,需要考虑用例的并发执行,因为之前做的项目是通过插件pytest-parallel 0.1.1 pytest-multithreading-allure 1.0.8来实现的,所以这次也打算用此方法,然而在实际使用过程中发现一些问题。 问题一 通…...
VO,PO,DTO
DTO(Data Transfer Object)数据传输对象 前后端之间的传输时使用 比如前端登录请求的请求参数有username,password,但后端pojo类user有username,password,birthday,gender时,可以创…...

Java设计模式-工厂
Java设计模式中,工厂模式主要包括普通工厂模式以及抽象工厂模式,普通工厂模式是用于制造输出不同类型的对象,抽象工厂模式是用于制造输出不同类型的普通工厂,本文主要描述工厂模式的基本用法。 如上所示,使用普通工厂模…...
【JavaEE】【1.3 Servlet】1.3.6 监听
什么是Servlet上下文? Servlet上下文(Servlet Context)是Java Servlet技术中的一个概念,它代表了一个Web应用程序的上下文环境。在Servlet规范中,每个Web应用程序都有一个唯一的Servlet上下文对象,该对象在…...

C#泛型委托
在C#中,delegate 关键字用于声明委托(delegates),委托是一种类型安全的函数指针,允许你传递方法作为参数或从方法返回方法。有时我们需要将一个函数作为另一个函数的参数,这时就要用到委托(Dele…...
从零开始精通RTSP之多播传输
概述 多播(Multicast)是一种高效的网络通信技术,它允许一台或多台主机(可称为多播源)发送单一数据包到多个目标主机(可称为多播组的成员),而只有属于该多播组的接收者才会接收到这些…...

(五)STM32F407 cubemx IIC驱动OLED(2)硬件篇
这篇文章主要是个人的学习经验,想分享出来供大家提供思路,如果其中有不足之处请批评指正哈。 废话不多说直接开始主题,本人是基于STM32F407VET6芯片,但是意在你看懂这篇文章后,不管是F1,F4,H7等一系列系统硬件IIC配…...

头歌实践教学平台:CG1-v1.0-点和直线的绘制
第5关:0<k<1直线绘制-中点算法 一.任务描述 根据下面要求,在右侧修改代码,绘制出预期输出的图片。平台会对你编写的代码进行测试。 1.本关任务 掌握一种基本图形元素光栅化算法,利用OpenGL实现直线光栅化的中点画线算法…...

java基础之面向对象的思想
一、面向对象和面向过程的编程思想对比 面向过程:是一种以过程为中心的编程思想,实现功能的每一步,都是自己实现的(自己干活)。 面向对象:是一种以对象为中心的编程思想,通过指挥对象实现具体的…...

红黑树的理解和简单实现
目录 1. 红黑树的概念和性质 2. 红黑树的插入 2.1. 情况一:新增节点的父亲为空 2.2. 情况二:新增节点的父亲非空且为黑色节点 2.3. 情况三:当父亲为红节点,叔叔存在且为红 2.3.1. 当祖父为根节点的时候 2.3.2. 当祖父不是根…...

发表博客之:gemm/threadblock/threadblock_swizzle.h 文件夹讲解,cutlass深入讲解
文章目录 [发表博客之:gemm/threadblock/threadblock_swizzle.h 文件夹讲解,cutlass深入讲解](https://cyj666.blog.csdn.net/article/details/138514145)先来看一下最简单的struct GemmIdentityThreadblockSwizzle结构体 发表博客之:gemm/th…...

【C语言项目】贪吃蛇(下)
个人主页~ 源码在Gitee仓库~ 上一篇贪吃蛇(上)~ 贪吃蛇 四、核心的实现游戏测试1、GameStart(1)控制台窗口大小和名字设置(2)光标隐藏(3)打印欢迎界面(4)创建…...
【Unity实战|热更】Addressable读取SO文件报错解决
情景再现 假定你有一个Unity工程,使用了HybridCLR和Addressable,SO文件存放在Addressable中。热更加载后进入游戏场景出现了SO文件读取报错: UnityEngine.AddressableAssets.InvalidKeyException: Exception of type UnityEngine.Addressab…...

Web自动化 - selenium
文章目录 一、selenium的使用selenium的安装 二、元素1. 定位选择元素1.id 定位2. class_name 定位find_element 和 find_elements的区别3. TAG_NAME 定位4. 超链接 定位 2. 操控元素1. 查询内容2. 获取元素文本内容3. 获取元素属性 3. 浏览器常用操作API4. 鼠标操作 - perform…...
基于select for update 实现数据库分布式锁
1、select for update 的基本语法 SELECT * FROM table_name WHERE condition FOR UPDATE;2、select for update 的定义及作用 2.1 、select for update的含义是在查询数据的同时对所选的数据行进行锁定,以保证数据的一致性和并发控制。在并发环境下,多…...

Java后端实现对象与文件接收数据(minio测试)
实现思路: 1. 两个接口实现,一个接对象数据(file),一个接文件数据(json)。 2. json对象(base64String) 实体类信息 ,请求体统一接收 3. file, String name ,String password ,String name , Controller层接收 统一…...

考研踩坑经验分享
文章目录 写在前面自身情况简介自身学习路线优点坑点 学习路线建议1、2和3月份3、4和5月份6、7和8月份9、10月份11、12月份 一些私货建议结尾 写在前面 考研是一件非常有盼头的事,但绝对不是一件容易的事。 如果你不能做好来年三月份出成绩时,坦然接受…...

Android Compose 一:基础控件
Flutter 与 Compose 组件辣么像,难道是同一个google团队整的;也未深究,只是猜测。 创建项目 需要使用新版本Android studio,忽略步骤… 项目目录 MainActivity说明 1 系统默认页面 Preview 修饰的方法,只用来供开发…...

linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...

elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
redis和redission的区别
Redis 和 Redisson 是两个密切相关但又本质不同的技术,它们扮演着完全不同的角色: Redis: 内存数据库/数据结构存储 本质: 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能: 提供丰…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...

Android写一个捕获全局异常的工具类
项目开发和实际运行过程中难免会遇到异常发生,系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler,它是Thread的子类(就是package java.lang;里线程的Thread)。本文将利用它将设备信息、报错信息以及错误的发生时间都…...

Axure Rp 11 安装、汉化、授权
Axure Rp 11 安装、汉化、授权 1、前言2、汉化2.1、汉化文件下载2.2、windows汉化流程2.3、 macOs汉化流程 3、授权 1、前言 Axure Rp 11官方下载链接:https://www.axure.com/downloadthanks 2、汉化 2.1、汉化文件下载 链接: https://pan.baidu.com/s/18Clf…...