Rotting Oranges

Similar Problems:

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.

Example 1:

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

Example 2:

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

Note:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// Blog link: https://code.dennyzhang.com/rotting-oranges // Basic Idea: BFS // Complexity: Time O(n), Space O(n) type point struct { i, j int } func orangesRotting(grid [][]int) int { row_count, col_count := len(grid), len(grid[0]) queue := []point{} for i, row := range grid { for j, val := range row { if val == 2 { queue = append(queue, point{i, j}) } } } level := -1 for len(queue) != 0 { l := []point{} for _, p := range queue { for _, offset := range [][]int{[]int{1, 0}, []int{-1, 0}, []int{0, 1}, []int{0, -1}} { i2, j2 := p.i + offset[0], p.j + offset[1] if i2<0 || i2>=row_count || j2<0 || j2>=col_count { continue } if grid[i2][j2] == 1 { grid[i2][j2] = 2 l = append(l, point{i2, j2}) } } } queue = l level++ } // check if good ones for _, row := range grid { for _, val := range row { if val == 1 { return -1 } } } if level == -1 { level = 0 } return level }