leetcode_solutions/
n1591_strange_printer_ii.rs

1/*
2 * No: 1591
3 * Title: Strange Printer II
4 */
5
6use crate::Solution;
7
8impl Solution {
9    pub fn is_printable(target_grid: Vec<Vec<i32>>) -> bool {
10        let mut graph: Vec<Vec<usize>> = vec![vec![]; 61];
11        let mut indegrees = vec![0 as usize; 61];
12
13        for color in 1..=60 {
14            Solution::search(&target_grid, color, &mut graph, &mut indegrees)
15        }
16
17        let mut deque = std::collections::VecDeque::<usize>::new();
18        let mut seen = std::collections::HashSet::<usize>::new();
19
20        for i in 0..61 {
21            if indegrees[i] == 0 {
22                deque.push_back(i);
23            }
24        }
25
26        while !deque.is_empty() {
27            let curr = deque.pop_front().unwrap();
28
29            if !seen.insert(curr) {
30                continue;
31            }
32
33            for neighbor in &graph[curr] {
34                indegrees[*neighbor] -= 1;
35                if indegrees[*neighbor] == 0 {
36                    deque.push_back(*neighbor);
37                }
38            }
39        }
40
41        seen.len() == 61
42    }
43
44    fn search(
45        grid: &Vec<Vec<i32>>,
46        color: i32,
47        graph: &mut Vec<Vec<usize>>,
48        indegrees: &mut Vec<usize>,
49    ) {
50        let mut x_min = usize::MAX;
51        let mut x_max = usize::MIN;
52        let mut y_min = usize::MAX;
53        let mut y_max = usize::MIN;
54
55        for x in 0..grid.len() {
56            for y in 0..grid[0].len() {
57                if grid[x][y] == color {
58                    x_min = std::cmp::min(x_min, x);
59                    x_max = std::cmp::max(x_max, x);
60                    y_min = std::cmp::min(y_min, y);
61                    y_max = std::cmp::max(y_max, y);
62                }
63            }
64        }
65
66        for x in x_min..=x_max {
67            for y in y_min..=y_max {
68                if grid[x][y] != color {
69                    graph[grid[x][y] as usize].push(color as usize);
70                    indegrees[color as usize] += 1;
71                }
72            }
73        }
74    }
75}
leetcode_solutions/n1591_strange_printer_ii.rs

leetcode_solutions/
n1591_strange_printer_ii.rs
