LeetCode 994. Rotting Oranges [Easy]

发表于 更新于 分类于 ， 阅读次数：

LeetCode 994. Rotting Oranges。

题目来源：https://leetcode.com/problems/rotting-oranges

题目难度：Easy

解答1[Java]：

核心思想

设时间为 minutes，初始时 minutes为0，初始状态就已经坏掉的橙子标记为2。

第一轮处理的时候，我们只处理 minutes + 2 的元素，把这种元素周围值为1的元素设为 minutes + 3。

这样一轮结束，我们把 minutes 加1，这样，刚刚被设为 minutes + 3 的元素，在minutes 加1之后，相当于变成了 minutes+2，也就是说，minutes+2一直代表上一轮变坏的橙子。

使用变量oldFresh 和 fresh 表示上一轮剩下的新鲜橙子数和本轮之后剩下的新鲜橙子数，如果两者相同，说明有一些新鲜的橙子碰不到坏橙子，不会变坏，直接返回 -1。

代码

1
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
33
34
35
36
37
38
public class Solution {
    public int orangesRotting(int[][] grid) {
        int fresh = 0, minutes = 0;
        for (int[] row : grid) {
            for (int element : row) {
                if (element == 1) {
                    ++fresh;
                }
            }
        }

        for (int oldFresh = fresh; fresh > 0; ++minutes, oldFresh = fresh) {
            for (int i = 0; i < grid.length; ++i) {
                for (int j = 0; j < grid[0].length; ++j) {
                    if (grid[i][j] == minutes + 2) {
                        fresh -= rot(grid, i + 1, j, minutes) +
                                rot(grid, i - 1, j, minutes) +
                                rot(grid, i, j + 1, minutes) +
                                rot(grid, i, j - 1, minutes);
                    }
                }
            }
            if (fresh == oldFresh) {
                return -1;
            }
        }
        return minutes;
    }
    
    // 判断g[i][j]这个元素是否可以会变坏，如果会变坏返回1，如果不会返回0
    private int rot(int[][] g, int i, int j, int d) {
        if (i < 0 || j < 0 || i >= g.length || j >= g[i].length || g[i][j] != 1) {
            return 0;
        }
        g[i][j] = d + 3;
        return 1;
    }
}

参考：C++/Java with picture, BFS

解答2[Java]：BFS广度优先遍历

核心思路

使用一个队列。第一次遍历的时候，把所有值为2的元素放到队列中。

开始遍历，每次只遍历上一轮放到队列中的元素，每遍历到一个元素，如果元素可以把周围的橙子变坏，就把变坏的橙子的值设为2，同时添加到队列中。

代码

1
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int countFresh = 0;
        //Put the position of all rotten oranges in queue
        //count the number of fresh oranges
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    countFresh++;
                }
            }
        }
        //if count of fresh oranges is zero --> return 0
        if (countFresh == 0) {
            return 0;
        }
        int count = 0;
        int[][] steps = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        //bfs starting from initially rotten oranges
        while (!queue.isEmpty()) {
            ++count;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] elementCoordinate = queue.poll();
                for (int[] step : steps) {
                    int x = elementCoordinate[0] + step[0];
                    int y = elementCoordinate[1] + step[1];
                    //if x or y is out of bound
                    //or the orange at (x , y) is already rotten
                    //or the cell at (x , y) is empty
                    //we do nothing
                    if (x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] == 0 || grid[x][y] == 2) {
                        continue;
                    }
                    //mark the orange at (x , y) as rotten
                    grid[x][y] = 2;
                    //put the new rotten orange at (x , y) in queue
                    queue.offer(new int[]{x, y});
                    //decrease the count of fresh oranges by 1
                    countFresh--;
                }
            }
        }
        return countFresh == 0 ? count - 1 : -1;
    }
}

参考：[Java] Clean BFS Solution with comments