当前位置:网站首页>Li Kou 994: rotten orange (BFS)
Li Kou 994: rotten orange (BFS)
2022-07-29 05:32:00 【Xiao Hong is working hard】
Simple breadth first search (BFS) problem : Store each batch of rotten oranges in a queue . Take out rotten oranges in batches , Take out the rotten orange and put in the fresh rotten orange .
import java.util.LinkedList;
import java.util.Queue;
class Solution {
int[][] dist = {
{
-1,0},{
1,0},{
0,1},{
0,-1}};// Up, down, left and right
public int orangesRotting(int[][] grid) {
int time = 0;// timing
Queue<int[]> queue = new LinkedList<int[]>();
int n = grid.length;
int m = grid[0].length;
boolean[][] booleans = new boolean[n][m];
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(grid[i][j] == 2){
// The first batch of rotten oranges is assigned true, Prevent repeated traversal
queue.offer(new int[]{
i,j});// Rotten oranges join the queue
booleans[i][j] = true;
}
if(grid[i][j] == 0){
// Empty cells are not processed , To prevent traversal, set the value to true
booleans[i][j] = true;
}
}
}
int[] a = new int[2];
while(!queue.isEmpty()){
int num = queue.size();// The number of rotten oranges in each batch
int flag = 0;// If rotten oranges can infect fresh oranges, it will change flag Value .
for(int number = 0;number < num;number++){
a = queue.poll();
for(int i = 0;i < 4;i++){
int x = a[0] + dist[i][0];
int y = a[1] + dist[i][1];
if(x>=0&&y>=0&&x<n&&y<m&&booleans[x][y]!=true){
grid[x][y] = 2;
queue.offer(new int[]{
x,y});
booleans[x][y] = true;
flag = 1;
}
}
}
if(flag == 1){
time++;
}
}
// Traverse all cells , If there are fresh oranges, return -1, Otherwise, return time .
for(int i = 0; i < n;i++){
for(int j = 0;j < m;j++){
if(grid[i][j] == 1){
return -1;
}
}
}
return time;
}
}
边栏推荐
猜你喜欢
365天挑战LeetCode1000题——Day 036 二叉树剪枝 + 子数组和排序后的区间和 + 删除最短的子数组使剩余数组有序
实现简单的数据库查询(不完整)
全局components组件注册
365 day challenge leetcode 1000 questions - day 040 design jump table + avoid flooding + find the latest grouping with size M + color ball with reduced sales value
哈夫曼树以及哈夫曼编码在文件压缩上的应用
[event preview] cloud development, efficient and intelligent - the second Alibaba cloud ECS cloudbuild developer competition is about to start
平行云CEO 李岩:CloudXR ,开启通往元宇宙的通道
365 day challenge leetcode1000 question - distance between bus stops on day 038 + time-based key value storage + array closest to the target value after transforming the array and + maximum value at t
QML type: mousearea
【剑指offer】— 详解库函数atoi以及模拟实现atoi函数
随机推荐
抽象类与接口
Live broadcast Preview: integration of JD cloud Devops and jfrog product library
MySQL的基础概念+数据库系统结构+拓展延申+基础命令学习
200 多家 ISV 入驻!阿里云计算巢发布一周年
Cryengine3 debugging shader method
【C语言系列】—文件操作详解(上)
B - 识别浮点常量问题
【C语言系列】— 把同学弄糊涂的 “常量” 与 “变量”
In depth analysis of common cross end technology stacks of app
Day 5
Complete ecological map of R & D Efficiency & selection of Devops tools
QML control: combobox
Camunda 1、Camunda工作流-介绍
Allocate memory: malloc() and free()
Global components component registration
阿里云架构师梁旭:MES on 云盒,助力客户快速构建数字工厂
Detailed explanation of serial port communication
阿里云联合鼎捷软件发布云上数字工厂解决方案,实现云MES系统本地化部署
京东云金秋上云特惠进行中!扫码参与活动
副作用和序列点