leetcode994-腐烂的橘子

原题

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

值 0 代表空单元格;
值 1 代表新鲜橘子;
值 2 代表腐烂的橘子。
每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。

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

示例 1:

leetcode994-腐烂的橘子

输入: [[2,1,1],[1,1,0],[0,1,1]] 输出: 4

示例 2:

输入: [[2,1,1],[0,1,1],[1,0,1]] 输出: -1
解释: 左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。

示例 3:

输入: [[0,2]] 输出: 0
解释: 因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。

提示:

  1. 1 <= grid.length <= 10
  2. 1 <= grid[0].length <= 10
  3. grid[i][j] 仅为 012

解法

思想

广度优先搜索,每次将搜索到的新鲜橘子搞成2,最后再搜索一遍全图是否有剩余的新鲜橘子。

代码

class Solution {
    int height;
    int width;
    public int orangesRotting(int[][] grid) {
        Queue<Integer> queue = new LinkedList<>();
        height = grid.length;
        if(height == 0) return 0;
        width = grid[0].length;
        for(int i = 0;i<height;i++){
            for(int j = 0;j<width;j++){
                if(grid[i][j]==2) queue.offer(i*width+j);
            }
        }
        queue.offer(null);
        int cur = 0;
        while(!queue.isEmpty()){
            Integer i = queue.poll();
            if(i==null){
                if(queue.isEmpty()) break;
                cur++;
                queue.offer(null);
                continue;
            }
            int x = i/width;
            int y = i%width;
            if(x!=0 && grid[x-1][y]==1){
                queue.offer(toInt(x-1,y));
                grid[x-1][y]=2;
            }
            if(x!=height-1 && grid[x+1][y]==1){
                queue.offer(toInt(x+1,y));
                grid[x+1][y]=2;
            }
            if(y!=0 && grid[x][y-1]==1) {
                queue.offer(toInt(x,y-1));
                grid[x][y-1]=2;
            }
            if(y!=width-1 && grid[x][y+1]==1) {
                queue.offer(toInt(x,y+1));
                grid[x][y+1]=2;
            }
        }
        for(int i = 0;i<height;i++){
            for(int j = 0;j<width;j++){
                if(grid[i][j]==1) return -1;
            }
        }
        return cur;
    }
    public int toInt(int x,int y){
        return x*width+y;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode994-%e8%85%90%e7%83%82%e7%9a%84%e6%a9%98%e5%ad%90/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月4日
下一篇 2020年3月4日

相关推荐

  • leetcode104-二叉树的最大深度

    原题 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例:给定二叉树 [3,9,20,null…

    算法 2020年1月11日
    090
  • leetcode498-对角线遍历

    这是一个Z字形编排问题,JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下…

    2019年11月14日
    0110
  • leetcode22-括号生成

    原题 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例: 输入:n = 3 输出:[ "((()))", "(()())", "…

    算法 2020年4月9日
    0130
  • leetcode410-分割数组的最大值

    原题 给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。 注意:数组长度 n 满足以下条件: 1…

    算法 2020年1月9日
    0680
  • leetcode430-扁平化多级双向链表

    原题 您将获得一个双向链表,除了下一个和前一个指针之外,它还有一个子指针,可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示…

    2019年12月17日
    0100
  • leetcode239-滑动窗口最大值

    原题 给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最…

    算法 2020年4月21日
    0180
  • leetcode117-填充每个节点的下一个右侧节点指针II

    原题 给定一个二叉树 struct Node {   int val;   Node *left;   Node *ri…

    2020年1月14日
    0370
  • leetcode70-爬楼梯

    原题 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意: 给定 n 是一个正整数。  示例 1: 输入:…

    算法 2020年1月21日
    0850
  • leetcode136-只出现一次的数字

    原题 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗…

    算法 2019年12月18日
    0150
  • leetcode509-斐波那契数

    原题 斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,   F(1) …

    算法 2020年1月21日
    0120

发表回复

登录后才能评论