##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/994.html

# 994. Rotting Oranges (Medium)

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.

Related Topics: Breadth-first Search

Similar Questions:

## Solution 1. BFS

// OJ: https://leetcode.com/problems/rotting-oranges/
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
int orangesRotting(vector<vector<int>>& A) {
int M = A.size(), N = A[0].size(), ans = 0, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
queue<pair<int, int>> q;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (A[i][j] == 2) q.emplace(i, j);
}
}
if (q.empty()) ans = 1;
while (q.size()) {
int cnt = q.size();
++ans;
while (cnt--) {
auto [x, y] = q.front();
q.pop();
for (auto &dir : dirs) {
int a = x + dir[0], b = y + dir[1];
if (a < 0 || a >= M || b < 0 || b >= N || A[a][b] != 1) continue;
A[a][b] = 2;
q.emplace(a, b);
}
}
}
for (auto &row : A) {
for (int x : row) {
if (x == 1) return -1;
}
}
return ans - 1;
}
};

• class Solution {
public int orangesRotting(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0)
return 0;
int rows = grid.length, columns = grid[0].length;
final int BLOCK = -1;
final int WHITE = 0;
final int GRAY = 1;
final int BLACK = 2;
int[][] colors = new int[rows][columns];
int[][] distances = new int[rows][columns];
Queue<int[]> queue = new LinkedList<int[]>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
int value = grid[i][j];
if (value == 2) {
distances[i][j] = 0;
colors[i][j] = GRAY;
queue.offer(new int[]{i, j});
} else if (value == 1) {
distances[i][j] = Integer.MAX_VALUE;
colors[i][j] = WHITE;
} else {
distances[i][j] = -1;
colors[i][j] = BLOCK;
}
}
}
int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int row = cell[0], column = cell[1];
int distance = distances[row][column];
for (int[] direction : directions) {
int newRow = row + direction[0], newColumn = column + direction[1];
if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns) {
if (colors[newRow][newColumn] == WHITE) {
distances[newRow][newColumn] = distance + 1;
colors[newRow][newColumn] = GRAY;
queue.offer(new int[]{newRow, newColumn});
}
}
}
colors[row][column] = BLACK;
}
int time = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
time = Math.max(time, distances[i][j]);
if (time == Integer.MAX_VALUE)
return -1;
}
}
return time == Integer.MAX_VALUE ? -1 : time;
}
}

############

class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
int cnt = 0;
Deque<int[]> q = new LinkedList<>();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 2) {
q.offer(new int[] {i, j});
} else if (grid[i][j] == 1) {
++cnt;
}
}
}
int ans = 0;
int[] dirs = {1, 0, -1, 0, 1};
while (!q.isEmpty() && cnt > 0) {
++ans;
for (int i = q.size(); i > 0; --i) {
int[] p = q.poll();
for (int j = 0; j < 4; ++j) {
int x = p[0] + dirs[j];
int y = p[1] + dirs[j + 1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
grid[x][y] = 2;
--cnt;
q.offer(new int[] {x, y});
}
}
}
}
return cnt > 0 ? -1 : ans;
}
}

• // OJ: https://leetcode.com/problems/rotting-oranges/
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
int orangesRotting(vector<vector<int>>& A) {
queue<pair<int, int>> q;
int M = A.size(), N = A[0].size(), step = 0, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (A[i][j] == 2) q.emplace(i, j);
}
}
while (q.size()) {
for (int cnt = q.size(); cnt--;) {
auto [x, y] = q.front();
q.pop();
for (auto &[dx, dy] : dirs) {
int a = x + dx, b = y + dy;
if (a < 0 || a >= M || b < 0 || b >= N || A[a][b] != 1) continue;
A[a][b] = 2;
q.emplace(a, b);
}
}
step++;
}
for (auto &row : A) {
for (int x : row) {
if (x == 1) return -1;
}
}
return max(0, step - 1);
}
};

• class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
q = deque()
cnt = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
q.append((i, j))
elif grid[i][j] == 1:
cnt += 1
ans = 0
while q and cnt:
ans += 1
for _ in range(len(q)):
i, j = q.popleft()
for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
cnt -= 1
grid[x][y] = 2
q.append((x, y))
return ans if cnt == 0 else -1

############

class Solution(object):
def orangesRotting(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
M, N = len(grid), len(grid[0])
fresh = 0
q = collections.deque()
for i in range(M):
for j in range(N):
if grid[i][j] == 1:
fresh += 1
elif grid[i][j] == 2:
q.append((i, j))
if fresh == 0:
return 0
dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]
step = 0
while q:
size = len(q)
for i in range(size):
x, y = q.popleft()
for d in dirs:
nx, ny = x + d[0], y + d[1]
if nx < 0 or nx >= M or ny < 0 or ny >= N or grid[nx][ny] != 1:
continue
grid[nx][ny] = 2
q.append((nx, ny))
fresh -= 1
step += 1
if fresh != 0:
return -1
return step - 1

• func orangesRotting(grid [][]int) int {
m, n := len(grid), len(grid[0])
cnt := 0
var q [][]int
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 2 {
q = append(q, []int{i, j})
} else if grid[i][j] == 1 {
cnt++
}
}
}
ans := 0
dirs := []int{-1, 0, 1, 0, -1}
for len(q) > 0 && cnt > 0 {
ans++
for i := len(q); i > 0; i-- {
p := q[0]
q = q[1:]
for j := 0; j < 4; j++ {
x, y := p[0]+dirs[j], p[1]+dirs[j+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 {
cnt--
grid[x][y] = 2
q = append(q, []int{x, y})
}
}
}
}
if cnt > 0 {
return -1
}
return ans
}

• function orangesRotting(grid: number[][]): number {
const m = grid.length;
const n = grid[0].length;
let count = 0;
const queue = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
count++;
} else if (grid[i][j] === 2) {
queue.push([i, j]);
}
}
}
let res = 0;
const dris = [1, 0, -1, 0, 1];
while (count !== 0 && queue.length !== 0) {
for (let i = queue.length; i > 0; i--) {
const [x, y] = queue.shift();
for (let j = 0; j < 4; j++) {
const newX = x + dris[j];
const newY = y + dris[j + 1];
if (
newX >= 0 &&
newX < m &&
newY >= 0 &&
newY <= n &&
grid[newX][newY] === 1
) {
grid[newX][newY] = 2;
queue.push([newX, newY]);
count--;
}
}
}
res++;
}
if (count != 0) {
return -1;
}
return res;
}


• use std::collections::VecDeque;

impl Solution {
pub fn oranges_rotting(mut grid: Vec<Vec<i32>>) -> i32 {
let mut queue = VecDeque::new();
let m = grid.len();
let n = grid[0].len();
// 新鲜橘子数量
let mut count = 0;
for i in 0..m {
for j in 0..n {
match grid[i][j] {
1 => count += 1,
2 => queue.push_back([i as i32, j as i32]),
_ => (),
}
}
}
let mut res = 0;
let dirs = [1, 0, -1, 0, 1];
while count != 0 && queue.len() != 0 {
let mut len = queue.len();
while len != 0 {
let [x, y] = queue.pop_front().unwrap();
for i in 0..4 {
let new_x = x + dirs[i];
let new_y = y + dirs[i + 1];
if new_x >= 0
&& new_x < m as i32
&& new_y >= 0
&& new_y < n as i32
&& grid[new_x as usize][new_y as usize] == 1
{
grid[new_x as usize][new_y as usize] = 2;
queue.push_back([new_x, new_y]);
count -= 1;
}
}
len -= 1;
}
res += 1;
}
if count != 0 {
return -1;
}
res
}
}