Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Rotten orange

The original address

In a given M x N grid, each cell can have one of the following three values:

  • value0Represents empty cells;
  • value1Is for fresh oranges;
  • value2Is for rotten oranges.

Every minute, fresh oranges in four directions around the rotting orange will rot.

Returns the minimum number of minutes that must pass until there are no fresh oranges in the cell. If that is not possible, return -1.

Example 1:

Input: grid = [[2.1.1], [1.1.0], [0.1.1]] output:4
Copy the code

Example 2:

Input: grid = [[2.1.1], [0.1.1], [1.0.1] Output: -1Explanation: The orange in the lower left corner (No2Ok, the first0Never rot, because rot only happens when4Theta is going up.Copy the code

Example 3:

Input: grid = [[0.2]] output:0Explanation: Because0There are no fresh oranges at the end of the minute, so the answer is0 。
Copy the code

Thought analysis

  1. First, count the total number of orangestotal, and the original location of the bad orangebadArr;
  2. To loop through an array of bad oranges with a length greater than zero, we first need to process the total number of orangestotal -= badArr.length; Dispose of the oranges around the bad oranges and store the location of the bad oranges in each roundtemp, and then updatebadArrAnd increase the number of roundsresultContinue the loop untilbadArrIs empty, indicating that there are no oranges that can be handled.
  3. The last judgmenttotalIf there are any unprocessed oranges, return- 1; Otherwise, returnresult.

AC code

/ * * *@param {number[][]} grid
 * @return {number}* /
var orangesRotting = function(grid) {
    const m = grid.length
    const n = grid[0].length
    let total = 0
    let result = 0
    let badArr = new Array(a)for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(grid[i][j] > 0){
                total++
                if(grid[i][j] === 2) badArr.push([i, j])
            }
        }
    }
    while(badArr.length > 0) {const temp = new Array()
        total -= badArr.length
        badArr.forEach(item= > {
            / /
            if(item[0] > =0 && item[1] + 1> =0 && item[0] < m && item[1] + 1 < n && grid[item[0]][item[1] + 1= = =1){
                grid[item[0]][item[1] + 1] = 2
                temp.push([item[0], item[1] + 1])}/ / right
            if(item[0] + 1> =0 && item[1] > =0 && item[0] + 1 < m && item[1] < n && grid[item[0] + 1][item[1= = =]]1){
                grid[item[0] + 1][item[1]] = 2
                temp.push([item[0] + 1, item[1]])}/ /
            if(item[0] > =0 && item[1] - 1> =0 && item[0] < m && item[1] - 1 < n && grid[item[0]][item[1] - 1= = =1){
                grid[item[0]][item[1] - 1] = 2
                temp.push([item[0], item[1] - 1])}/ / left
            if(item[0] - 1> =0 && item[1] > =0 && item[0] - 1 < m && item[1] < n && grid[item[0] - 1][item[1= = =]]1){
                grid[item[0] - 1][item[1]] = 2
                temp.push([item[0] - 1, item[1]])
            }
        })
        badArr = temp
        if(badArr.length > 0)
            result++
    }
    return total === 0 ? result : -1
};
Copy the code

Results:

  • Result: Yes
  • Execution time: 68 ms, beating 89.01% of all JavaScript commits
  • Memory consumption: 43.6 MB, beating 42.32% of all JavaScript commits
  • Pass test case: 306/306

END