Leetcode994腐烂的橘子(广度搜索法)

2022-03-10 22:39:02 浏览数 (2)

Leetcode994腐烂的橘子

在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:

值 0 代表空单元格;

值 1 代表新鲜橘子;

值 2 代表腐烂的橘子。

每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

答题:

```

/**

* @param {number[][]} grid

* @return {number}

*/

var orangesRotting = function(grid) {

let m = grid.length

let n = grid[0].length

let queue = []

let total = 0

let count_2 = 0

let count_1 = 0

for(let i=0;i<m;i ){

​ for(let j =0;j<n;j ){

​ if(grid[i][j] === 2){

​ count_2 = 1

​ total

​ queue.push([i,j])

​ }else if(grid[i][j] === 1){

​ total

​ count_1 =1

​ }

​ }

}

if (count_2 === total) return 0

if (count_1 === total) return -1

let count = 0

while(queue.length){

​ let size = queue.length

​ let exit = false

​ for(let k=0;k<size;k ){

​ let [i,j] = queue.shift()

​ if(i-1>= 0 && grid[i-1][j] === 1){

​ queue.push([i-1,j])

​ grid[i-1][j] = 2

​ exit = true

}

​ if(j-1>= 0 && grid[i][j-1] === 1){

​ queue.push([i,j-1])

​ grid[i][j-1] = 2

​ exit = true

​ }

​ if(i 1<m && grid[i 1][j] === 1){

​ queue.push([i 1,j])

​ grid[i 1][j] = 2

​ exit = true

​ }

​ if(j 1<n && grid[i][j 1] === 1){

​ queue.push([i,j 1])

​ grid[i][j 1] = 2

exit = true

​ }

​ }

​ if(exit){

​ count

​ }

}

for(let i=0;i<m;i ){

​ for(let j=0;j<n;j ){

​ if(grid[i][j] === 1){

​ return -1

​ }

​ }

}

return count

};

```

重点是有些特殊情况要处理下,比如没有坏橘子的时候返回啥,没有好橘子的时候返回啥,什么情况下时间 1,什么情况下跳过走下一步。具体认真看下代码就好了。

0 人点赞