BFS1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33class Solution {
public int orangesRotting(int[][] grid) {
if(grid==null||grid.length==0) return -1;
Queue<int[]> q=new LinkedList<>();
int time=0;
int freshOrange=0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j]==1) freshOrange++;
if(grid[i][j]==2) q.offer(new int[]{i,j});
}
}
int[][] directions={{-1,0},{1,0},{0,1},{0,-1}};
while(!q.isEmpty()&&freshOrange>0){
int queueSize=q.size();
for(int i=0;i<queueSize;i++){
int[] rotten=q.poll();
for(int[] d:directions){
int newI=rotten[0]+d[0];
int newJ=rotten[1]+d[1];
if(newI>=0&&newI<grid.length&&newJ>=0&&newJ<grid[0].length&&grid[newI][newJ]==1){
grid[newI][newJ]=2;
freshOrange--;
q.offer(new int[]{newI,newJ});
}
}
}
time++;
}
return freshOrange==0?time:-1;
}
}