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
|
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::collections::HashMap;
const N: usize = 200;
const M: usize = 200;
pub fn dist(input: &Vec<Vec<u32>>, y1: i32, x1: i32, y2: i32, x2: i32) -> i32 {
let ind1 = (y1 - y2).abs();
let ind2 = (x1 - x2).abs();
if (ind1 == 1 && ind2 == 0) || (ind1 == 0 && ind2 == 1) {
return input[y2 as usize][x2 as usize] as i32;
}
return i32::MAX;
}
pub fn main() {
let txt = std::fs::read_to_string("./input/day17.txt").unwrap();
let input = txt
.lines()
.map(|s| {
s.split("")
.filter_map(|c| c.parse::<u32>().ok())
.collect::<Vec<_>>()
})
.collect::<Vec<Vec<_>>>();
let n = input.len();
let m = input[0].len();
let mut d = [[i32::MAX; M]; N];
// (dist, y, x, dy, dx, cnt)
let mut bh: BinaryHeap<Reverse<(i32, i32, i32, i32, i32, i32)>> = Default::default();
// (y, x, dy, dx, cnt)
let mut hm: HashMap<(i32, i32, i32, i32, i32), bool> = Default::default();
bh.push(Reverse((0, 0, 0, 0, 1, 0)));
bh.push(Reverse((0, 0, 0, 1, 0, 0)));
hm.insert((0, 0, 0, 1, 0), true);
hm.insert((0, 0, 1, 0, 0), true);
while !bh.is_empty() {
let Reverse(x) = bh.pop().unwrap();
let (ndist, i, j, odi, odj, cnt) = x;
if ndist < d[i as usize][j as usize] && cnt >= 4 {
d[i as usize][j as usize] = ndist;
}
for (di, dj) in [(0, 1), (0, -1), (1, 0), (-1, 0)] {
if odi == -di && odj == -dj {
continue;
}
if cnt < 4 && !(odi == di && odj == dj) {
continue;
}
let ni = i + di;
let nj = j + dj;
if ni < 0 || ni >= n as i32 || nj < 0 || nj >= m as i32 {
continue;
}
let ncnt = if di == odi && dj == odj { cnt + 1 } else { 1 };
let ndst = ndist + dist(&input, i, j, ni, nj);
if hm.contains_key(&(ni, nj, di, dj, ncnt)) || ncnt == 11 {
continue;
} else {
hm.insert((ni, nj, di, dj, ncnt), true);
}
bh.push(Reverse((ndst, ni, nj, di, dj, ncnt)));
}
}
println!("{}", d[n - 1][m - 1]);
}
|
