994. Rotting Oranges

Description of Problem

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent 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.

Example 1:

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

Example 2:

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

Constraints:

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

Solution

Tags: Breadth First Search

Explanation

Very simple, just use BFS to simulate the process of rotting oranges.

Code (Rust)

#[derive(Clone, Copy, Debug, PartialEq)]
enum Colour{
    White,
    Gray,
    Black,
}
use Colour::{White, Gray, Black};

impl Solution {
    pub fn oranges_rotting(grid: Vec<Vec<i32>>) -> i32 {
        use std::collections::VecDeque;

        let m = grid.len();
        let n = grid[0].len();

        let mut colours = vec![ vec![White ;n];m ];
        
        let mut depth = 0;
        let mut queue1 = VecDeque::new();
        let mut queue2 = VecDeque::new();

        let mut count_rotten = 0;
        let mut count_fresh = 0;
        
        // Put all rotten organges into queue1
        for i in 0..m{
            for j in 0..n{
                if grid[i][j] == 2 {
                    queue1.push_back((i,j));
                    colours[i][j] = Black;
                    count_rotten+=1;
                }else if grid[i][j] == 1 {
                    count_fresh+=1;
                }
            }
        }

        // Deal with special cases
        // Case 1: The grid has no fresh oranges
        if count_fresh == 0  {
            return 0;
        }
        // Case 2: The grid has only fresh oranges
        else if count_rotten == 0{
            return -1;
        }

        // Case 3: The grid has fresh oranges and rotton oranges
        while !queue1.is_empty(){
            while let Some((i,j)) = queue1.pop_front(){
                // UP
                if Self::is_available(&grid, &colours, i-1, j, m, n) {
                    colours[i-1][j] = Gray;
                    queue2.push_back((i-1, j));
                }
                // LEFT
                if Self::is_available(&grid, &colours, i, j-1, m, n) {
                    colours[i][j-1] = Gray;
                    queue2.push_back((i,j-1));
                }
                // RIGHT
                if Self::is_available(&grid, &colours, i, j+1, m, n) {
                    colours[i][j+1] = Gray;
                    queue2.push_back((i,j+1));
                }
                // BOTTOM
                if Self::is_available(&grid, &colours, i+1, j, m, n) {
                    colours[i+1][j] = Gray;
                    queue2.push_back((i+1,j));
                }
                // Finish the exploration of the node
                colours[i][j] = Black;
            }
            depth+=1;
            let temp = queue1;
            queue1 = queue2;
            queue2 = temp;
        }

        // Check whether all oranges are rotten?
        for i in 0..m{
            for j in 0..n{
                if colours[i][j] != Black && (grid[i][j] == 2 || grid[i][j] == 1) {
                    return - 1;
                }
            }
        }

        return depth - 1;
    }

    #[inline(always)]
    fn is_available(
        grid: &Vec<Vec<i32>>, 
        colours : &Vec<Vec<Colour>>,
        i : usize,
        j : usize,
        m : usize,
        n : usize
    ) -> bool {
        return 
            0 <= i && i < m 
            && 0 <= j && j < n 
            && grid[i][j] == 1
            && colours[i][j] == White
        ;
    }
}

Complexity

Time Complexity

\( T(m,n) = O(m \cdot n) \)

Leetbook