leetcode 994. Rotting Oranges

Description:

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent 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.

Example 1:

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

Example 2:

Input: grid = [[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: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

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

基础BFS
不过自己写为什么总是花时间排查小毛病呢？

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int numOfFresh = 0;
        queue<pair<int, int>> Q;
        for(int i = 0; i < grid.size(); ++i){//发霉橘子入队
            for(int j = 0; j < grid[0].size(); ++j){
                if(grid[i][j] == 2){
                    Q.push(pair<int,int>(i,j));
                }
                if(grid[i][j] == 1){
                    ++numOfFresh;
                }
            }
        }
        int step[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
        int t = -1;
        if(Q.empty()&& (numOfFresh == 0)) return 0;//bug点1
        if(Q.empty()) return -1;
        while(!Q.empty()){
            ++t;
            int size = Q.size();
            for(int i = 0; i < size; ++i){
                int x = Q.front().first;
                int y = Q.front().second;
                Q.pop();
                for(int j = 0; j < 4; ++j){
                    if(isFresh(grid,x+step[j][0], y+step[j][1])){
                        --numOfFresh;
                        grid[x+step[j][0]][y+step[j][1]] = 2;
                        Q.push(pair<int,int>(x+step[j][0], y+step[j][1]));
                    }
                }
            }
        }
        if(numOfFresh == 0) return t;
        else return -1;
    }
    bool isFresh(vector<vector<int>>& grid,int i, int j){
        if((i >= grid.size())||(i < 0)) return false; //bug点2
        if((j >= grid[i].size())||(j < 0)) return false;
        if(grid[i][j] == 1) return true;
        return false;
    }
};

bug点1：没有考虑清这几种情况:

没有发霉的橘子（但有正常的橘子）
没有任何橘子

bug点2: 判越界我一开始为什么没有判断if(x < 0)呢？？？？