

import java.util.LinkedList
;
import java.util.Queue
;
public
class H994 {
public
int orangesRotting(
int[][] grid) {
int rows=grid.length;
int cols=grid[0].length;
Queue<
int[]> que=
new LinkedList<
>(
)
;
int fresh=0
;
for(
int i=0
;i<rows;i++
)
{
for(
int j=0
;j<cols;j++
)
{
if(grid[i][j]==2
)
{
que.offer(
new
int[]{
i,j
}
)
;
}
if(grid[i][j]==1
)
{
fresh++
;
}
}
}
if(fresh==0
)
return 0
;
int[][] dirs={
{
1
,0
}
,{
0
,1
}
,{
0
,-1
}
,{
-1
,0
}
}
;
int minutes=0
;
while(!que.isEmpty(
)
)
{
int size=que.size(
)
;
boolean rotted=false
;
for(
int i=0
;i<size;i++
)
{
int[] pos=que.poll(
)
;
int x=pos[0]
;
int y=pos[1]
;
for(
int[] dir:dirs)
{
int nextx=x+dir[0]
;
int nexty=y+dir[1]
;
if(nextx>=0&&nextx<rows&&nexty>=0&&nexty<cols&&grid[nextx][nexty]==1
)
{
grid[nextx][nexty]=2
;
fresh--
;
que.offer(
new
int[]{
nextx,nexty
}
)
;
rotted=true
;
}
}
}
if(rotted==true
)
{
minutes++
;
}
}
if(fresh==0
)
{
return minutes;
}
else {
return -1
;
}
}
public
static
void main(String[] args)
{
int[][] grid={
{
2
,1
,1
}
,{
1
,1
,0
}
,{
0
,1
,1
}
}
;
H994 test=
new H994(
)
;
int result=test.orangesRotting(grid)
;
System.out.print(result)
;
}
}