【LeetCode】 994. 腐烂的橘子 2020年3月4日

旧城等待， 2021-06-10 20:38 342阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 思路 ###

1.  每个坏橘子四周的好橘子，每一分钟之后都会变成坏橘子，呈现了一种扩散的效果，其实这恰好对应了图的广度遍历，我们就可以借助队列来实现这道题目
2.  每遍历一次，把遍历到的橘子的坐标放进队列中，下次再根据队列中的橘子进行下一次遍历。

### code ###

class Solution { 
        public int orangesRotting(int[][] grid) { 
            int rows = grid.length;
            int cols = grid[0].length;
            Queue<Point> queue = new LinkedList<>();
            int count0 = 0;
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cols; j++) { 
                    if (grid[i][j] == 2) queue.add(new Point(i, j));
                    else if (grid[i][j] == 0) count0++;
                }
            }
            if (count0 == rows * cols) return 0; // 如果没有橘子，返回 0
            if (queue.isEmpty()) return -1; // 如果没有坏橘子，返回-1
            int mins = 0;
            while (!queue.isEmpty()) { 
                int size = queue.size();
                for (int i = 0; i < size; i++) { 
                    Point point = queue.poll();
                    int x = point.x;
                    int y = point.y;
                    if (x > 0 && grid[x - 1][y] == 1) {  // 上面的橘子
                        queue.add(new Point(x - 1, y));
                        grid[x - 1][y] = 2;
                    }
                    if (x < rows - 1 && grid[x + 1][y] == 1) {  // 下面的橘子
                        queue.add(new Point(x + 1, y));
                        grid[x + 1][y] = 2;
                    }
                    if (y > 0 && grid[x][y - 1] == 1) {  // 左面的橘子
                        queue.add(new Point(x, y - 1));
                        grid[x][y - 1] = 2;
                    }
                    if (y < cols - 1 && grid[x][y + 1] == 1) {  // 右面的橘子
                        queue.add(new Point(x, y + 1));
                        grid[x][y + 1] = 2;
                    }
                }
                mins++; // 每一轮过后增加一分钟
            }
    
            // 判断还有没有没坏的
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cols; j++) { 
                    if (grid[i][j] == 1) return -1;
                }
            }
    
            return mins - 1;
        }
    
    }
    
    class Point { 
        int x;
        int y;
    
        Point(int x, int y) { 
            this.x = x;
            this.y = y;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/rotting-oranges/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/663186a9d224467f9509d6fb39e7796b.png