腐烂的橘子 力扣bfs

BFS用来搜索最短路径的解法是比较合适的。

比如求最少步数的解,最少交换次数的解,最快走出迷宫等等,因为bfs搜索过程中遇到的第一个解一定是离最初位置最近的,所以遇到第一个解,一定就是最优解,此时搜索算法可以终止。

DFS用来搜索全部的解。

class Solution {
public://bfs最短路径 队列
   int dis[11][11],cut,ans,tx,ty;
   int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
    int orangesRotting(vector<vector<int>>& grid) {
     queue<pair<int,int>>q;//队里存的都是腐烂的橘子
     memset(dis,-1,sizeof(dis));
    int n=grid.size(),m=grid[0].size(),i,j;
    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
    {
        if(grid[i][j]==2)//腐烂
        {
            q.push(make_pair(i,j));
            dis[i][j]=0;
//现在所有腐烂的橘子的位置都是0,其他位置是-1,这个用来记录时间,还可以标志这个位置的橘子是否新鲜
        }
        else if(grid[i][j]==1)//新鲜
        cut++;
    }
    while(!q.empty()){
        pair<int,int>x=q.front();q.pop();
       for(i=0;i<4;i++)
       {
         tx=dx[i]+x.first;
         ty=dy[i]+x.second;
if(tx>=0&&tx<n&&ty>=0&&ty<m&&grid[tx][ty]!=0&&dis[tx][ty]==-1)
   { dis[tx][ty]=dis[x.first][x.second]+1;//这个背腐烂的橘子的时间是传染给他腐烂的橘子加1
      q.push(make_pair(tx,ty));//加入新腐烂的橘子
        cut--;
        ans=max(ans,dis[tx][ty]);
        if(cut==0) break;
       }}   }
    return cut?-1:ans;  }};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/460929.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

表单修饰符和事件修饰符

表单修饰符和事件修饰符 表单修饰符 v-model.lazy v-model.lazy 失去焦点后再收集数据 <div id"app"><textarea name"" id"" cols"30" rows"10" v-model.lazy"a"></textarea>{{a}}<textar…

水果音乐编曲和制作软件 FL Studio 中文汉化破解版下载 FL Studio 中文设置教程

FL Studio 21 也就是 Image-Line 出品的一款功能强大的编曲软件&#xff0c;全名 Fruity Loops Studio 简称“FL Studio”。 FL Studio 21.2汉化破解版是功能强大的音乐制作解决方案&#xff0c;使用旨在为用户提供一个友好完整的音乐创建环境&#xff0c;让您能够轻松创建、管…

【ansible】ansible的介绍和安装

前言运维自动化 云计算核心职能 搭建平台架构 日常运营保障 性能效率优化 相关工具 代码管理&#xff08;SCM&#xff09;&#xff1a;GitHub、GitLab、BitBucket、SubVersion 构建工具&#xff1a;maven、Ant、Gradle 自动部署&#xff1a;Capistrano、CodeDeploy 持续…

JVM-5

1.选择垃圾收集器 如果你的堆大小不是很大&#xff08;比如 100MB &#xff09;&#xff0c;选择串行收集器一般是效率最高的。 参数&#xff1a; -XX:UseSerialGC 。如果你的应用运行在单核的机器上&#xff0c;或者你的虚拟机核数只有单核&#xff0c;选择串行收集器依然是合…

P6技巧:ORACLE Primavera P6 反馈项目Reflections的使用

前言 反馈是一个有趣的概念&#xff0c;就目前的了解而言&#xff0c;他是 Primavera P6 所独有的。 你可以将反馈视为项目的特殊假设副本。 然而&#xff0c;与直接拷贝副本不同的是&#xff0c;反馈保留了返回源项目的链接。 这意味着如果反馈发生更改&#xff0c;你可以将部…

Javascript 线性搜索算法

线性搜索被定义为一种顺序搜索算法&#xff0c;从一端开始&#xff0c;遍历列表中的每个元素&#xff0c;直到找到所需的元素&#xff0c;否则搜索将继续&#xff0c;直到数据集的末尾。 线性搜索算法 线性搜索算法如何工作&#xff1f; 在线性搜索算法中&#xff1a; …

C++语法、Linux命令查询网站

文章目录 1.cplusplus2.cppreference3.Linux命令查询网站 1.cplusplus 网址&#xff1a;https://legacy.cplusplus.com/ 2.cppreference 1.cppreference中文网站&#xff1a;https://zh.cppreference.com/w/首页 2.cppreference英文原站&#xff1a;https://en.cppreference…

openssl3.2 - note - Decoders and Encoders with OpenSSL

文章目录 openssl3.2 - note - Decoders and Encoders with OpenSSL概述笔记编码器/解码器的调用链OSSL_STORE 编码器/解码器的名称和属性OSSL_FUNC_decoder_freectx_fnOSSL_FUNC_encoder_encode_fn官方文档END openssl3.2 - note - Decoders and Encoders with OpenSSL 概述 …

【STM32学习】PWM学习,(二)驱动LED呼吸灯

上文学习了PWM的基本概述&#xff0c;和PWM的各种参数&#xff0c;本文 学习使用PWM信号去驱动LED实现呼吸灯的效果。 1、PWM驱动LED呼吸灯 1.1介绍 目标&#xff1a;单片机输出一个PWM信号&#xff0c;驱动LED呼吸亮灭。PWM占空比高&#xff0c;则LED更亮&#xff1b;PWM占空…

第12章 指针

以下内容是学习尚硅谷 12.1 指针基本介绍 1&#xff09;指针是C语言的精华&#xff0c;也是C语言的难点 2&#xff09;指针&#xff0c;也就是内存的地址&#xff1b;所谓指针变量&#xff0c;也就是保存了内存地址的变量。关于指针的基本使用&#xff0c;在讲变量的时候做了…

【SCI论文】“学术丑闻揭露:当AI写作遭遇学术审稿,ChatGPT意外成为论文共作者!“

在最近的学术圈中出现了一篇令人哭笑不得的论文。这篇文章标题为“The three-dimensional porous mesh structure of Cu-base…”发表在《Surfaces and Interfaces》杂志上&#xff0c;竟然包含了ChatGPT的提示语&#xff0c;暴露出了审稿过程中可能的疏忽。 文章讨论了铜基金…

【四 (5)数据可视化之 Pyecharts常用图表及代码实现 】

目录 文章导航一、介绍[✨ 特性]二、安装Pyecharts三、主题风格四、占比类图表1、饼图2、环形图3、玫瑰图4、玫瑰图-多图5、堆叠条形图6、百分比堆叠条形图 五、比较排序类1、条形图2、雷达图3、词云图4、漏斗图 六、趋势类图表1、折线图2、堆叠折线图3、面积图4、堆叠面积图 七…

Linux:kubernetes(k8s)有状态的服务部署(14)

之前我都是对无状态进行的一个操作&#xff0c;我们想扩容就扩容&#xff0c;想缩容就缩容&#xff0c;根本不用去考虑他的一个网络环境&#xff0c;本地储存环境啥的一个状态 当我们做有状态的服务的操作&#xff0c;肯定要申请一个持久化的一个空间&#xff0c;以及网络&…

tcp/ip协议2实现的插图,数据结构8 (30 - 32章)

(201) 201 三十0 中断优先级补充 (202) 202 三十1 TCP的用户需求 函tcp_usrreq一 (203) 203 三十2 TCP的用户需求 函tcp_usrreq二 (204) 204 三十3 TCP的用户需求 函tcp_usrreq三 (205) 205 三十4 TCP的用户需求 函tcp_usrreq四 (206) 206 三十5 TCP的用户需求 函tcp_usrreq五 …

邮件协议(SMTP、POP3、IMAP4)

电子邮件系统 1、概述 &#xff08;1&#xff09;网络电子邮件系统&#xff0c;好处在于价格低廉&#xff0c;速度非常快 &#xff08;2&#xff09;形式多样化&#xff08;文字、图像、声音……&#xff09; 2、电子邮件系统组成部分 用户代理 MUA&#xff08;Mail User …

【调参】如何为神经网络选择最合适的学习率lr-LRFinder-for-Keras

【调参】如何为神经网络选择最合适的学习率lr-LRFinder-for-Keras_学习率选择-CSDN博客文章浏览阅读9.2k次&#xff0c;点赞6次&#xff0c;收藏55次。keras 版本的LRFinder&#xff0c;借鉴 fast.ai Deep Learning course。前言学习率lr在神经网络中是最难调的全局参数&#x…

java抽象类的作用及解析

在 Java 中&#xff0c;抽象类是一种特殊的类&#xff0c;它可以用于定义一些抽象的方法和属性&#xff0c;这些方法和属性可能在子类中有不同的实现。 抽象类的主要作用包括&#xff1a; 提供抽象方法&#xff1a;抽象类可以包含一些没有具体实现的抽象方法&#xff0c;这些…

德人合科技 | 公司办公终端、电脑文件资料 \ 数据透明加密防泄密管理软件系统

天锐绿盾是一款全面的企业级数据安全解决方案&#xff0c;它专注于为企业办公终端、电脑文件资料提供数据透明加密防泄密管理。 首页 德人合科技——www.drhchina.com 这款软件系统的主要功能特点包括&#xff1a; 1. **透明加密技术**&#xff1a; 天锐绿盾采用了透明加密技…

〔理论与代码分析〕Fast-SCNN:Fast Semantic Segmentation Network(语义分割、经典网络、速度、高效、实时)

论文地址&#xff1a;Fast-SCNN: Fast Semantic Segmentation Network论文提出时间&#xff1a;2019 年 2 月 12 日官方代码&#xff1a;作者并没有放出源代码&#xff0c;因此下面是一些第三方的实现 PaddleSeg 复现代码&#xff1a;百度飞桨团队复现的代码MMSegmentation 复现…

Spring Boot+Vue前后端分离项目如何部署到服务器

&#x1f31f; 前言 欢迎来到我的技术小宇宙&#xff01;&#x1f30c; 这里不仅是我记录技术点滴的后花园&#xff0c;也是我分享学习心得和项目经验的乐园。&#x1f4da; 无论你是技术小白还是资深大牛&#xff0c;这里总有一些内容能触动你的好奇心。&#x1f50d; &#x…
最新文章