1
use std::collections::{HashSet, VecDeque};
2

3
const DIRECTIONS: [(isize, isize); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];
4
impl Solution {
5
  pub fn oranges_rotting(grid: Vec<Vec<i32>>) -> i32 {
6
    let mut queue = VecDeque::new();
7
    let mut seen = HashSet::new();
8
    let mut minutes = 0;
9

10
    // fill the queue with all rotten oranges
11
    for i in 0..grid.len() {
12
      for j in 0..grid[0].len() {
13
        if grid[i][j] == 2 {
14
          queue.push_back((i as isize, j as isize, 0));
15
          seen.insert((i, j));
16
        }
17
      }
18
    }
19

20
    // perform bfs and spread rotting orange
21
    while let Some((i, j, time)) = queue.pop_front() {
22
      for &(di, dj) in &DIRECTIONS {
23
        let next_i = i + di;
24
        let next_j = j + dj;
25

26
        if next_i >= 0
27
          && next_j >= 0
28
          && next_i < grid.len() as isize
29
          && next_j < grid[0].len() as isize
30
          && !seen.contains(&(next_i as usize, next_j as usize))
31
          && grid[next_i as usize][next_j as usize] == 1
32
        {
33
          queue.push_back((next_i, next_j, time + 1));
34
          seen.insert((next_i as usize, next_j as usize));
35
          minutes = time + 1;
36
        }
37
      }
38
    }
39

40
    // make sure all oranges are rotted; if any aren't then its impossible to rot all oranges
41
    for i in 0..grid.len() {
42
      for j in 0..grid[0].len() {
43
        if grid[i][j] == 1 && !seen.contains(&(i, j)) {
44
          return -1;
45
        }
46
      }
47
    }
48

49
    minutes
50
  }
51
}