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