当前位置: 首页 > news >正文

腐烂的橘子BFS

题目: 腐烂的橘子

在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:

每分钟,腐烂的橘子 周围 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

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

什么是分库分表

读写分离主要应对的是数据库读并发&#xff0c;没有解决数据库存储问题。试想一下&#xff1a;如果 MySQL 一张表的数据量过大怎么办? 答案当然是分库分表 什么是分库&#xff1f; 分库 就是将数据库中的数据分散到不同的数据库上&#xff0c;可以垂直分库&#xff0c;也可…...

pytest并发执行用例方案

背景 开始做新项目的UI自动化&#xff0c;需要考虑用例的并发执行&#xff0c;因为之前做的项目是通过插件pytest-parallel 0.1.1 pytest-multithreading-allure 1.0.8来实现的&#xff0c;所以这次也打算用此方法&#xff0c;然而在实际使用过程中发现一些问题。 问题一 通…...

VO,PO,DTO

DTO&#xff08;Data Transfer Object&#xff09;数据传输对象 前后端之间的传输时使用 比如前端登录请求的请求参数有username&#xff0c;password&#xff0c;但后端pojo类user有username&#xff0c;password&#xff0c;birthday&#xff0c;gender时&#xff0c;可以创…...

Java设计模式-工厂

Java设计模式中&#xff0c;工厂模式主要包括普通工厂模式以及抽象工厂模式&#xff0c;普通工厂模式是用于制造输出不同类型的对象&#xff0c;抽象工厂模式是用于制造输出不同类型的普通工厂&#xff0c;本文主要描述工厂模式的基本用法。 如上所示&#xff0c;使用普通工厂模…...

【JavaEE】【1.3 Servlet】1.3.6 监听

什么是Servlet上下文&#xff1f; Servlet上下文&#xff08;Servlet Context&#xff09;是Java Servlet技术中的一个概念&#xff0c;它代表了一个Web应用程序的上下文环境。在Servlet规范中&#xff0c;每个Web应用程序都有一个唯一的Servlet上下文对象&#xff0c;该对象在…...

C#泛型委托

在C#中&#xff0c;delegate 关键字用于声明委托&#xff08;delegates&#xff09;&#xff0c;委托是一种类型安全的函数指针&#xff0c;允许你传递方法作为参数或从方法返回方法。有时我们需要将一个函数作为另一个函数的参数&#xff0c;这时就要用到委托&#xff08;Dele…...

从零开始精通RTSP之多播传输

概述 多播&#xff08;Multicast&#xff09;是一种高效的网络通信技术&#xff0c;它允许一台或多台主机&#xff08;可称为多播源&#xff09;发送单一数据包到多个目标主机&#xff08;可称为多播组的成员&#xff09;&#xff0c;而只有属于该多播组的接收者才会接收到这些…...

(五)STM32F407 cubemx IIC驱动OLED(2)硬件篇

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

头歌实践教学平台:CG1-v1.0-点和直线的绘制

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

java基础之面向对象的思想

一、面向对象和面向过程的编程思想对比 面向过程&#xff1a;是一种以过程为中心的编程思想&#xff0c;实现功能的每一步&#xff0c;都是自己实现的&#xff08;自己干活&#xff09;。 面向对象&#xff1a;是一种以对象为中心的编程思想&#xff0c;通过指挥对象实现具体的…...

红黑树的理解和简单实现

目录 1. 红黑树的概念和性质 2. 红黑树的插入 2.1. 情况一&#xff1a;新增节点的父亲为空 2.2. 情况二&#xff1a;新增节点的父亲非空且为黑色节点 2.3. 情况三&#xff1a;当父亲为红节点&#xff0c;叔叔存在且为红 2.3.1. 当祖父为根节点的时候 2.3.2. 当祖父不是根…...

发表博客之:gemm/threadblock/threadblock_swizzle.h 文件夹讲解,cutlass深入讲解

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

【C语言项目】贪吃蛇(下)

个人主页~ 源码在Gitee仓库~ 上一篇贪吃蛇&#xff08;上&#xff09;~ 贪吃蛇 四、核心的实现游戏测试1、GameStart&#xff08;1&#xff09;控制台窗口大小和名字设置&#xff08;2&#xff09;光标隐藏&#xff08;3&#xff09;打印欢迎界面&#xff08;4&#xff09;创建…...

【Unity实战|热更】Addressable读取SO文件报错解决

情景再现 假定你有一个Unity工程&#xff0c;使用了HybridCLR和Addressable&#xff0c;SO文件存放在Addressable中。热更加载后进入游戏场景出现了SO文件读取报错&#xff1a; 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的含义是在查询数据的同时对所选的数据行进行锁定&#xff0c;以保证数据的一致性和并发控制。在并发环境下&#xff0c;多…...

Java后端实现对象与文件接收数据(minio测试)

实现思路&#xff1a; 1. 两个接口实现&#xff0c;一个接对象数据(file)&#xff0c;一个接文件数据(json)。 2. json对象(base64String) 实体类信息 &#xff0c;请求体统一接收 3. file, String name ,String password ,String name &#xff0c; Controller层接收 统一…...

考研踩坑经验分享

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

Android Compose 一:基础控件

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

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

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

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

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

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

Android写一个捕获全局异常的工具类

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

Axure Rp 11 安装、汉化、授权

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