专栏首页编程理解Leetcode 994. 腐烂的橘子

Leetcode 994. 腐烂的橘子

题目描述

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

  • 值 0 代表空单元格;
  • 值 1 代表新鲜橘子;
  • 值 2 代表腐烂的橘子。

每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1。

广度优先遍历

腐烂橘子的传播以一种类似广播扩散的形式进行。这里不妨以队列来模拟腐烂橘子的扩散过程,队列中存储新的被感染的橘子,则队列为空时表示扩散停止。此时若网格中仍有新鲜橘子,则表示这些橘子不可达,返回 -1;若全部橘子均为腐烂,则返回扩散次数(可能为 0,即初始情况即为全部腐烂)。

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        cnt,l,w=0,len(grid),len(grid[0]) 
        arr=[(i,j) for i in range(l) for j in range(w) if grid[i][j]==2]
        while arr:
            for t in range(len(arr)):
                i,j=arr.pop(0)
                for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                    if 0<=x<l and 0<=y<w and grid[x][y]==1:
                        arr.append((x,y))
                        grid[x][y]=2
            if arr:
                cnt+=1
        arr=[(i,j) for i in range(l) for j in range(w) if grid[i][j]==1]
        return -1 if arr else cnt

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 234. 回文链表

    若要满足 O(1) 空间复杂度,则不能借助于列表或栈结构存储数据。因为单链表不像字符串可以进行直接访问,所以这里采用的方式为,找到单链表中间元素,并反转单链表前...

    zhipingChen
  • Leetcode 300. 最长上升子序列

    申请等长的临时数组 arr,用于保存每个位置上对应的最长上升序列长度,则计算 arr[i] 时,需要遍历前 i 个位置,取 nums 值小于 nums[i] 的...

    zhipingChen
  • 动态规划(二):0-1背包

    代码中存在两层循环,以二维数组的形式记录中间数据,分别记录不同物品个数在各个空间大小下的最大价值。循环内部存在两种判断,分别用于判断空间大小

    zhipingChen
  • 阮一峰快速排序

    本打算学一波快速排序,查了查资料,吓一大跳,说阮一峰大神的快排是不对的,以此开始了一大波大神针对这个问题的各种观点。感兴趣的可以看看知乎这篇帖子:

    wade
  • 详解Python中的生成器表达式(generator expression)

    生成器表达式(generator expression)也叫生成器推导式或生成器解析式,用法与列表推导式非常相似,在形式上生成器推导式使用圆括号(parenth...

    Python小屋屋主
  • Sort Algorithm

    生成随机的n个数量的数组,输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性,所以需要一个验证正确性和计算排序时间的:

    西红柿炒鸡蛋
  • 常见排序算法及golang 实现

    快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有...

    程序员养成日记
  • 数据结构与算法 基础排序(O(n^2))

    不能直接找到一个比minIndex小的就swap,因为交换后比较的就是minIndex和后一个元素2个元素的比较 而不是minIndex和后面所有元素比较

    g小志
  • Data Structure_Sort Algorithm

    生成随机的n个数量的数组,输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性,所以需要一个验证正确性和计算排序时间的:

    西红柿炒鸡蛋
  • python for循环

    当range执行完之后,代码执行else部分代码。如果遇到break,终止循环,不会走else代码

    py3study

扫码关注云+社区

领取腾讯云代金券