Leetcode - rotting-oranges

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.

The solution is very simple by using BFS. Using a queue to store rotten oranges, iterating the queue and find fresh oranges around the rotten one, set fresh one to rotten and enqueue. After a round of rotting, pop previous round of rotten oranges.

func orangesRotting(grid [][]int) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return -1
    }

    queue := [][]int{}
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            if grid[i][j] == 2 {
                queue = append(queue, []int{i, j})
            }
        }
    }
    count := 0
    for len(queue) != 0 {
        size := len(queue)
        for k := 0; k < size; k++ {
            i := queue[k][0]
            j := queue[k][1]
            if i > 0 && grid[i-1][j] == 1 {
                grid[i-1][j]++
                queue = append(queue, []int{i - 1, j})
            }
            if i < len(grid)-1 && grid[i+1][j] == 1 {
                grid[i+1][j]++
                queue = append(queue, []int{i + 1, j})
            }
            if j > 0 && grid[i][j-1] == 1 {
                grid[i][j-1]++
                queue = append(queue, []int{i, j - 1})
            }
            if j < len(grid[i])-1 && grid[i][j+1] == 1 {
                grid[i][j+1]++
                queue = append(queue, []int{i, j + 1})
            }
        }
        queue = queue[size:]
        if len(queue) == 0 {
            break
        }
        count++

    }

    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            if grid[i][j] == 1 {
                return -1
            }
        }
    }

    return count
}

# @param {Integer[][]} grid
# @return {Integer}
def oranges_rotting(grid)
    return -1 if grid.length == 0 || grid[0].length == 0
    queue = []
    for i in 0..grid.length-1
        for j in 0..grid[0].length-1
            queue << [i, j] if grid[i][j] == 2
        end
    end
    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    count = 0
    while queue.length != 0
        size = queue.length
        for k in 0..size-1
            p = queue[k]
            x = p[0]
            y = p[1]
            directions.each do |d|
                new_x = x + d[0]
                new_y = y + d[1]
                if new_x >= 0 && new_y >= 0 && new_x < grid.length && new_y < grid[0].length && grid[new_x][new_y] == 1
                    queue << [new_x, new_y]
                    grid[new_x][new_y] = 2
                end
            end
        end
        queue = queue[size..-1]
        break if queue.length == 0
        count += 1
    end
    
    for i in 0..grid.length-1
        for j in 0..grid[0].length-1
            return -1 if grid[i][j] == 1
        end
    end
    
    return count
end

• 相关文章
• 全局相关文章