腐烂的橘子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 修饰的方法,只用来供开发…...
光伏产业发展带动紧固件需求增长 市场趋势与应用分析 上海紧固件专业展
2026第十六届上海紧固件专业展(Fastener Expo Shanghai 2026)将于6月24日至26日在上海国家会展中心举行。随着新能源产业持续升温,光伏行业的快速发展正在显著带动紧固件市场需求增长,成为行业关注的重要方向。在全球能源转型的大…...
保姆级教程:用华为eNSP复现一个能跑通的企业网毕业设计(含VRRP、OSPF、防火墙策略)
华为eNSP企业网实战:从零构建高可用网络架构 刚接触网络工程的学生或初级工程师,面对企业级网络设计时常常陷入配置迷雾——为什么这里要用VRRP?OSPF区域划分的依据是什么?防火墙策略如何与NAT协同工作?本文将以华为eN…...
Z-Image-Turbo_Sugar脸部Lora模型服务运维指南:监控、日志与故障排查
Z-Image-Turbo_Sugar脸部Lora模型服务运维指南:监控、日志与故障排查 最近在帮一个做创意设计的朋友维护他们的AI图像生成服务,他们用的就是Z-Image-Turbo_Sugar这个专门生成特定风格人脸的Lora模型。朋友跟我吐槽,说服务时不时就“抽风”&a…...
从零到一:深度解析BertTokenizer.from_pretrained的加载机制与实战技巧
1. 初识BertTokenizer.from_pretrained:你的NLP敲门砖 第一次接触Hugging Face的Transformers库时,我被BertTokenizer.from_pretrained()这个方法深深吸引了。它就像是一把万能钥匙,能快速打开各种预训练语言模型的大门。记得当时我尝试用传统…...
Argos Translate:5分钟掌握开源离线翻译API的全面集成方案
Argos Translate:5分钟掌握开源离线翻译API的全面集成方案 【免费下载链接】argos-translate Open-source offline translation library written in Python 项目地址: https://gitcode.com/GitHub_Trending/ar/argos-translate Argos Translate是一款基于Ope…...
运算放大器入门难?这篇超详细运算放大器原理与应用指南帮你轻松上手!
1. 运算放大器到底是什么? 第一次接触运算放大器时,我也被这个专业名词吓到了。但后来发现,它其实就是个"超级放大镜"——能把微弱的电信号放大成千上万倍。想象一下医生用的听诊器,它能将微弱的心跳声放大到清晰可闻&a…...
Cogito v1预览版3B模型实战体验:超越Llama/DeepSeek的混合推理能力
Cogito v1预览版3B模型实战体验:超越Llama/DeepSeek的混合推理能力 1. 模型概览与核心优势 1.1 什么是Cogito v1预览版 Cogito v1预览版是Deep Cogito推出的混合推理模型系列,这个3B参数的版本在多项基准测试中表现优异。与传统的语言模型不同&#x…...
高效开源输入法词库转换实战指南:30+格式无缝互转技巧
高效开源输入法词库转换实战指南:30格式无缝互转技巧 【免费下载链接】imewlconverter ”深蓝词库转换“ 一款开源免费的输入法词库转换程序 项目地址: https://gitcode.com/gh_mirrors/im/imewlconverter 深蓝词库转换是一款功能强大的开源输入法词库转换工…...
【论文】信息系统项目管理师范围管理要点
本资料摘自《科科过论文集分析》,底部附PDF图片版记忆。项目管理中范围管理的六大核心环节,旨在为专业写作提供具体的实践指导与案例素材。文档强调在描述规划、需求收集和范围定义时,应避免枯燥的理论堆砌,转而通过真实的业务场景…...
DanKoe 视频笔记:每日60分钟改变生活:引言与概述
在本教程中,我们将学习如何通过每天投入60分钟来系统地改变生活。我们将探讨常规的重要性,并介绍三个核心习惯,帮助你重新掌控精力、提升财务状况、改善健康以及获得内心的清晰。 每日60分钟改变生活:2:常规的必要性 …...
