java leetcode之[动态规划 中等]994. 腐烂的橘子

题目的链接在这里：https://leetcode-cn.com/problems/rotting-oranges/

目录

• 题目大意
• 一、示意图
• 二、解题思路
• • 多维BFS

题目大意

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

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

一、示意图

二、解题思路

多维BFS

多维BFS

代码如下：

class Solution {
public int orangesRotting(int[][] grid) {//0表示空格 1表示新鲜桔子 2表示腐烂的桔子 用来统计时间 要么就是先统计 这个新鲜桔子的数量int count=0;int time=0;Queue<int[]> queue=new LinkedList<>();for(int i=0;i<grid.length;i++){for(int j=0;j<grid[0].length;j++){if(grid[i][j]==1){count++;}//如果是腐烂橘子 那就需要放进去了if(grid[i][j]==2){queue.add(new int[]{i,j});}}}//这里进行初始判断 如果直接count等于0了 那就是0 了if(count==0){return 0;}//然后就需要 进行判断int [][] step={{0,1},{0,-1},{-1,0},{1,0}};while (!queue.isEmpty()){//每次都是时间加一time++;int size=queue.size();for(int i=0;i<size;i++){//然后从他的四周开始扩散int[] poll = queue.poll();for(int j=0;j<4;j++){int newX=poll[0]+step[j][0];int newY=poll[1]+step[j][1];//然后就是判断 没有越界 然后是新鲜的桔子吧if(newX>=0&&newX<grid.length&&newY>=0&&newY<grid[0].length&&grid[newX][newY]==1){//那就把他变成不是新鲜桔子 并且 桔子总数减1count--;//然后进队列grid[newX][newY]=2;queue.add(new int[]{newX,newY});}}}}//最后判断 新鲜桔子有没有全都变成不新鲜的return count==0?time-1:-1;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！