LeetCode994 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:

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

Example 2:

1
2
3

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:

1
2
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.

思路

Step1: 统计数组中的新鲜橘子的个数，统计腐败橘子并记录腐败橘子的位置，将记录的值放入数组中。

int fresh=0;
Queue<int[]> q = new LinkedList();
for(int x=0;x<grid.length;x++)
    for(int y=0;y<grid[0].length;y++){
        if(grid[x][y]==1)
            fresh++;
        else if(grid[x][y]==2){
            int array[]={x,y};
            q.add(array);
        }
    }

Step2: 设定方向数组direction[1,0,-1,0,1] 因为每个腐败橘子会让其上下左右腐败，根据方向进行BFS。

int minutes=0;
int direction[]={1,0,-1,0,1};
while(fresh!=0 && !q.isEmpty()){
    int size = q.size();
    while(size!=0){
        int arr[]=q.remove();
        int x=arr[0];
        int y=arr[1];
        for(int i=0;i<4;i++){
            int dx=x+direction[i];
            int dy=y+direction[i+1];
            if(dx<0||dx>=grid.length||dy<0||dy>=grid[0].length||grid[dx][dy]!=1)
                continue;
            fresh--;
            grid[dx][dy]=2;
            int n[]={dx,dy};
            q.add(n);
        }
        size--;
    }
    minutes++;
}

Step3：因为会存在与腐败橘子不相邻的新鲜橘子，因此当fresh不为0时，返回-1.

1
2
3

if(fresh==0)
    return minutes;
return -1;