java leetcode之[动态规划 中等]994. 腐烂的橘子
2021/11/24 11:39:56
本文主要是介绍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){ //那就把他变成不是新鲜桔子 并且 桔子总数减1 count--; //然后进队列 grid[newX][newY]=2; queue.add(new int[]{newX,newY}); } } } } //最后判断 新鲜桔子有没有全都变成不新鲜的 return count==0?time-1:-1; } }
这篇关于java leetcode之[动态规划 中等]994. 腐烂的橘子的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)