题目

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:
image.png

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

Example 2:

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

Example 3:

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

Note:

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

题意

给定一个矩阵包含若干个新鲜橘子和烂橘子。每一分钟每个烂橘子相邻四个橘子都会腐烂，问经过几分钟只剩下烂橘子。

思路

先遍历一遍矩阵，将所有烂橘子的位置加入队列，并统计新鲜橘子的个数。每一分钟的过程相当于将当前队列中位置全部出栈，判断相邻4个位置是否有新鲜橘子，有则将其变为烂橘子并将其位置加入队列以便下一分钟的处理。最后判断还有没有新鲜橘子。

代码实现

Java

  1. class Solution {
  2.     public int orangesRotting(int[][] grid) {
  3.         int count = 0;
  4.         int minutes = 0;
  5.         int[] xPlus = { 0, 1, 0, -1 };
  6.         int[] yPlus = { 1, 0, -1, 0 };
  7.         int m = grid.length, n = grid[0].length;
  8.         Queue<Coor> q = new LinkedList<>();
  10.         for (int i = 0; i < m; i++) {
  11.             for (int j = 0; j < n; j++) {
  12.                 if (grid[i][j] == 2) {
  13.                     q.offer(new Coor(i, j));
  14.                 } else if (grid[i][j] == 1) {
  15.                     count++;
  16.                 }
  17.             }
  18.         }
  20.         while (!q.isEmpty()) {
  21.             int size = q.size();
  23.             for (int j = 0; j < size; j++) {
  24.                 Coor cur = q.poll();
  25.                 for (int i = 0; i < 4; i++) {
  26.                     int nextX = cur.x + xPlus[i];
  27.                     int nextY = cur.y + yPlus[i];
  28.                     if (isValid(m, n, nextX, nextY) && grid[nextX][nextY] == 1) {
  29.                         grid[nextX][nextY] = 2;
  30.                         count--;
  31.                         q.offer(new Coor(nextX, nextY));
  32.                     }
  33.                 }
  34.             }
  36.             if (!q.isEmpty()) minutes++;
  37.         }
  39.         return count == 0 ? minutes : -1;
  40.     }
  42.     private boolean isValid(int m, int n, int i, int j) {
  43.         return i >= 0 && i < m && j >= 0 && j < n;
  44.     }
  45. }
  47. class Coor {
  48.     int x;
  49.     int y;
  51.     public Coor(int x, int y) {
  52.         this.x = x;
  53.         this.y = y;
  54.     }
  55. }