# Leetcode: Rotting Oranges

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. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. 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
}
```

Share It, If You Like It.