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
76
77
78
79
80
81
82
83
84
85
86
87
|
use std::collections::HashMap;
fn bfs(
input: &Vec<Vec<char>>,
was: &mut Vec<Vec<bool>>,
x: i32,
y: i32,
dx: i32,
dy: i32,
comb: &mut HashMap<(i32, i32, i32, i32), i32>,
) {
if x < 0
|| x >= input[0].len() as i32
|| y < 0
|| y >= input.len() as i32
|| comb.contains_key(&(x, y, dx, dy))
{
return;
}
let c = input[y as usize][x as usize];
was[y as usize][x as usize] = true;
comb.insert((x, y, dx, dy), 1);
if c == '/' {
bfs(input, was, x - dy, y - dx, -dy, -dx, comb);
} else if c == '\\' {
bfs(input, was, x + dy, y + dx, dy, dx, comb);
} else if c == '|' {
if dy != 0 {
bfs(input, was, x + dx, y + dy, dx, dy, comb);
} else {
bfs(input, was, x, y - 1, 0, -1, comb);
bfs(input, was, x, y + 1, 0, 1, comb);
}
} else if c == '-' {
if dx != 0 {
bfs(input, was, x + dx, y + dy, dx, dy, comb);
} else {
bfs(input, was, x - 1, y, -1, 0, comb);
bfs(input, was, x + 1, y, 1, 0, comb);
}
} else if c == '.' {
bfs(input, was, x + dx, y + dy, dx, dy, comb);
}
}
fn try_comb(input: &Vec<Vec<char>>, x: i32, y: i32, dx: i32, dy: i32) -> usize {
let mut was = vec![vec![false; input[0].len()]; input.len()];
let mut comb = HashMap::new();
bfs(&input, &mut was, x, y, dx, dy, &mut comb);
let mut sum = 0;
for i in was {
sum += i.iter().filter(|&n| *n == true).count();
}
return sum;
}
pub fn main() {
let txt = std::fs::read_to_string("./input/day16.txt").unwrap();
let input = txt
.lines()
.map(|s| s.chars().collect::<Vec<char>>())
.collect::<Vec<Vec<char>>>();
let mut m = 0;
for i in 0..input.len() {
m = usize::max(m, try_comb(&input, 0, i as i32, 1, 0));
m = usize::max(
m,
try_comb(&input, (input[0].len() - 1) as i32, i as i32, -1, 0),
);
}
for i in 0..input[0].len() {
m = usize::max(m, try_comb(&input, i as i32, 0, 0, 1));
m = usize::max(
m,
try_comb(&input, i as i32, (input.len() - 1) as i32, 0, -1),
);
}
println!("{}", m);
}
|
