1  #![feature(test)]
 2  
 3  use std::{cmp::Reverse, collections::BinaryHeap};
 4  
 5  use rustc_hash::FxHashSet;
 6  
 7  type Input = Vec<Vec<u32>>;
 8  
 9  fn setup(input: &str) -> Input {
10      input
11          .lines()
12          .map(|line| line.chars().map(|c| (c as u32) - 0x30).collect())
13          .collect()
14  }
15  
16  fn dijkstra(grid: &Input, k: usize) -> u32 {
17      let w = grid[0].len();
18      let h = grid.len();
19      let mut queue = BinaryHeap::new();
20      queue.push(Reverse((0u32, 0usize, 0usize)));
21      let mut visited = FxHashSet::default();
22      while !queue.is_empty() {
23          let (d, x, y) = queue.pop().unwrap().0;
24  
25          if visited.contains(&(x, y)) {
26              continue;
27          }
28          visited.insert((x, y));
29  
30          if x == w * k - 1 && y == h * k - 1 {
31              return d;
32          }
33  
34          for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)] {
35              let p = (x as i32) + dx;
36              let q = (y as i32) + dy;
37              if p < 0 || q < 0 {
38                  continue;
39              }
40              let p = p as usize;
41              let q = q as usize;
42              if p >= k * w || q >= k * h {
43                  continue;
44              }
45              if visited.contains(&(p, q)) {
46                  continue;
47              }
48              let c = grid[q % h][p % w] + (q / h + p / w) as u32;
49              queue.push(Reverse((d + (c - 1) % 9 + 1, p, q)));
50          }
51      }
52      panic!();
53  }
54  
55  fn part1(input: &Input) -> String {
56      dijkstra(input, 1).to_string()
57  }
58  
59  fn part2(input: &Input) -> String {
60      dijkstra(input, 5).to_string()
61  }
62  
63  aoc::main!(2021, 15, ex: 1);