Leetcode 994, rotten orange

994、 Rotten oranges

1） Title Description

In the given m x n grid grid in , Each cell can have one of three values ：

• value 0 For empty cells ;
• value 1 For fresh oranges ;
• value 2 For rotten oranges .

Every minute , Rotten oranges Around 4 Adjacent in two directions All fresh oranges rot .

return The minimum number of minutes that must elapse until there are no fresh oranges in the cell . If not , 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
 explain ： Orange in the lower left corner （ The first  2  That's ok ,  The first  0  Column ） Never rot , Because decay happens only in  4  Positive upward .

Example 3：

 Input ：grid = [[0,2]]
 Output ：0
 explain ： because  0  There are no fresh oranges by minute , So the answer is  0 .

Tips ：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] Only for 0、1 or 2

2） analysis

Breadth first search .

• Traverse grid Where to store all rotten oranges , The team , And count the number of fresh oranges ;
• Then traverse the queue , If there are fresh oranges around , Then set the time , Then add it to the queue , Reduce the number of fresh oranges by one ;
• After breadth first search , If the number of fresh oranges is not zero , return -1.

3）C++ Code

class Solution {
    
public:
    int orangesRotting(vector<vector<int>>& grid) {
    
        int m=grid.size();
        int n=grid[0].size();
        int dx[4]={
    1,0,-1,0};
        int dy[4]={
    0,1,0,-1};
        int cnt_1=0;
        int res=0;
        queue<pair<int,int>> que;
        vector<vector<int>> timeCosted(m,vector<int> (n,0));


        // Traversing the grid , Record the coordinates of all rotten oranges and the number of fresh oranges 
        for(int i=0;i<m;i++){
    
            for(int j=0;j<n;j++){
    
                if(grid[i][j]==2)
                    que.emplace(i,j);
                else if(grid[i][j]==1)
                    cnt_1++;
            }
        }

        // Breadth first search 
        while(!que.empty()){
    
            int x=que.front().first;
            int y=que.front().second;
            que.pop();
            for(int i=0;i<4;i++){
    
                int newX=x+dx[i];
                int newY=y+dy[i];
                if(newX>=0&&newX<m&&newY>=0&&newY<n&&grid[newX][newY]==1&&!timeCosted[newX][newY]){
    
                    timeCosted[newX][newY]=timeCosted[x][y]+1;
                    que.emplace(newX,newY);
                    if(grid[newX][newY]==1){
    
                        res=res>timeCosted[newX][newY]?res:timeCosted[newX][newY];
                        cnt_1-=1;
                        if(!cnt_1)
                            break;
                    }
                }
            }
        }
        return cnt_1?-1:res;
    }
};