跳转至

994.Rotting Oranges

Tags: Easy Breadth-first Search

Links: https://leetcode.com/problems/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:

img

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. 1 <= grid.length <= 10
  2. 1 <= grid[0].length <= 10
  3. grid[i][j] is only 0, 1, or 2.
class Solution {
    int direction[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    struct Node {
        int x, y;
        Node(int x, int y) : x(x), y(y) {}
    };
public:
    int orangesRotting(vector<vector<int>>& grid) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = grid.size(), n = grid[0].size();
        queue<Node> q;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 2) q.push(Node(i, j));
            }
        }

        int cnt = 0;
        while (!q.empty()) {
            int len = q.size();
            for (int i = 0; i < len; ++i) {
                Node tmp = q.front(); q.pop();
                for (int j = 0; j < 4; ++j) {
                    int row = tmp.x + direction[j][0];
                    int col = tmp.y + direction[j][1];
                    if (0 <= row && row < m && 0 <= col && col < n && grid[row][col] == 1) {
                        grid[row][col] = 2;
                        q.push(Node(row, col));
                    }
                }
            }
            ++cnt;
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) return -1;
            }
        }

        return cnt ? --cnt : 0;
    }
};

这道题两个注意点，一个是把最初每个腐烂的橘子当作广搜的起始点，到了把所有橘子都变成腐烂，也就是最后一层，cnt还是在计数，但是此时已经满足题目要求，所以当cnt不为零的时候，需要对cnt减一。cnt为零的情况是初始没有腐烂的橘子，也没有新鲜的橘子，所以这两点要小心。