# 994. Rotting Oranges

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:

Input: [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.

24 ms 38.6 MB

```class Solution {
public int orangesRotting(int[][] grid) {
if(this.nothing(grid)){
return 0;
}
if(this.neverR(grid)){
return -1;
}

int count = 0;
while(!this.isAllR(grid)){
grid = this.infect(grid);

count ++;
if(count > grid.length * grid[0].length){
return -1;
}
}
return count;
}

public int[][] infect(int[][] grid){
int[][] next = new int[grid.length][grid[0].length];
for(int x  = 0; x < grid.length; x ++){
for(int y = 0; y < grid[0].length; y++){
next[x][y] = grid[x][y];
}
}
for(int x  = 0; x < grid.length; x ++){
for(int y = 0; y < grid[0].length; y++){
if(grid[x][y] == 2){
if(x>0 && next[x-1][y] > 0){
next[x-1][y] = 2;
}
if(y>0 && next[x][y-1] > 0){
next[x][y-1] = 2;
}
if(x< grid.length-1 && next[x+1][y] > 0){
next[x+1][y] = 2;
}
if(y < grid[0].length - 1 && next[x][y+1] > 0){
next[x][y+1] = 2;
}
}
}
}
return next;
}

public boolean isAllR(int[][] grid){
boolean allR = true;
for (int[] col : grid){
for (int c : col){
if(c == 1){
allR = false;
}
}
}
return allR;
}

public boolean neverR(int[][] grid){
boolean allFresh = true;
for(int x  = 0; x < grid.length; x ++){
for(int y = 0; y < grid[0].length; y++){

if(grid[x][y] == 2){
allFresh = false;
}

if(grid[x][y] == 1){

boolean alone = true;
if(x>0 && grid[x-1][y] != 0){
alone = false;
}
if(y>0 && grid[x][y-1] != 0){
alone = false;
}
if(x< grid.length-1 && grid[x+1][y] != 0){
alone = false;
}
if(y < grid[0].length - 1 && grid[x][y+1] != 0){
alone = false;
}
System.out.println(alone);
if(alone){
return true;
}
}
}
}
return allFresh;
}

public boolean nothing(int[][] grid){
boolean nothing = true;
for(int x  = 0; x < grid.length; x ++){
for(int y = 0; y < grid[0].length; y++){

if(grid[x][y] > 0){
nothing = false;
}

}
}
return nothing;
}
}```