当前位置:网站首页>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;
}
}
边栏推荐
- Live broadcast Preview: integration of JD cloud Devops and jfrog product library
- Live broadcast preview | how to save 30% labor cost and shorten 80% trademark processing cycle?
- 英伟达周锡健:设计到数字营销的最后一公里
- Common shortcut keys for Ad
- Container security open source detection tool - veinmind (mirror backdoor, malicious samples, sensitive information, weak password, etc.)
- Live broadcast preview | how to improve enterprise immunity through "intelligent edge security"?
- QML control: combobox
- R & D efficiency | analysis of kubernetes' core technology and Devops' landing experience
- MySQL的详细安装使用教程(保姆式安装图文讲解)
- The road to success in R & D efficiency of 1000 person Internet companies
猜你喜欢
ClickHouse学习(十一)clickhouseAPI操作
Live broadcast preview | how to save 30% labor cost and shorten 80% trademark processing cycle?
365天挑战LeetCode1000题——Day 036 二叉树剪枝 + 子数组和排序后的区间和 + 删除最短的子数组使剩余数组有序
AiTalk创始人梁宇淇:镜像连接虚拟与现实的纽带
Helm chart for Kubernetes
Li Yan, CEO of parallel cloud: cloudxr, opens the channel to the metauniverse
实现简单的数据库查询(不完整)
哈夫曼树以及哈夫曼编码在文件压缩上的应用
C语言 一维数组
如视技术副总裁杨永林:当传统产业遇到“数字空间”
随机推荐
167. Sum of two numbers II - enter an ordered array
C语言 一级指针
365天挑战LeetCode1000题——Day 036 二叉树剪枝 + 子数组和排序后的区间和 + 删除最短的子数组使剩余数组有序
【C语言系列】—文件操作详解(上)
Alibaba cloud architect details nine trends in the game industry
一维数组练习
Introduction to array learning simple question sum of two numbers
Thousands of databases, physical machines all over the country, JD logistics full volume cloud live record | interview with excellent technical team
QML custom tabbar
Custom QML control: imagebutton
C语言文件操作
关于局部变量
321, Jingdong Yanxi × Nlpcc 2022 challenge starts!
WDDM learning
With cloud simulation platform, Shichuang technology supports the upgrading of "China smart manufacturing"
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 control: combobox
Topological ordering of a graph of water
冒泡排序 C语言
Camunda 1、Camunda工作流-介绍