diff options
Diffstat (limited to '12/src/part-2.rs')
-rw-r--r-- | 12/src/part-2.rs | 120 |
1 files changed, 120 insertions, 0 deletions
diff --git a/12/src/part-2.rs b/12/src/part-2.rs new file mode 100644 index 0000000..aa14ef8 --- /dev/null +++ b/12/src/part-2.rs @@ -0,0 +1,120 @@ +mod tensor; + +use std::collections::{BinaryHeap}; +use std::io::{BufRead}; + +use tensor::{Index, Shape, Tensor}; + +#[derive(Debug)] +struct Node { + idx: [usize; 2], + cost: usize +} + +impl Node { + fn new(idx: [usize; 2], cost: usize) -> Self { + Self { + idx: idx, + cost: cost + } + } +} + +impl PartialEq for Node { + fn ne(self: & Self, other: & Self) -> bool { + self.cost != other.cost + } + fn eq(self: & Self, other: & Self) -> bool { + self.cost == other.cost + } +} + +impl Eq for Node { +} + +impl PartialOrd for Node { + fn partial_cmp(self: & Self, other: & Self) -> Option<std::cmp::Ordering> { + other.cost.partial_cmp(& self.cost) + } +} + +impl Ord for Node { + fn cmp(self: & Self, other: & Self) -> std::cmp::Ordering { + other.cost.cmp(& self.cost) + } +} + +fn main() { + let stdin = std::io::stdin(); + let mut handle = stdin.lock(); + + let mut buf: Vec<u8> = Vec::new(); + + let mut tmp: Vec<(u8, bool)> = Vec::new(); + let mut m: usize = 0; + let mut n: usize = 0; + let mut n_check: usize = 0; + + loop { + let buf = handle.fill_buf().expect("IO error"); + let bytes_read = buf.len(); + if bytes_read == 0 { break; } + + for & b in buf.into_iter() { + if b == b'\n' { + m += 1; + assert_eq!(n_check, n); + n_check = 0; + } + else { + tmp.push((b, false)); + if m == 0 { + n += 1; + } + n_check += 1; + } + } + + handle.consume(bytes_read); + } + let mut terrain: Tensor<(u8, bool), 2> = Tensor::new_from([m, n], tmp); + + let mut unvisited: BinaryHeap<Node> = BinaryHeap::new(); + let mut done: bool = false; + let mut res: usize = usize::MAX; + + for i in 0..m { + for j in 0..n { + if terrain[[i, j]].0 == b'E' { + unvisited.push(Node::new([i, j], 0)); + } + } + } + + while let Some(node) = unvisited.pop() { + let idx = node.idx; + if !terrain[idx].1 { + let elev = if terrain[idx].0 == b'E' { b'z' } else { terrain[idx].0 }; + let neighbor_idxs = [[idx[0].wrapping_sub(1), idx[1] ], + [idx[0] + 1 , idx[1] ], + [idx[0] , idx[1].wrapping_sub(1)], + [idx[0] , idx[1] + 1 ]]; + for neighbor_idx in neighbor_idxs.into_iter() { + if let Some(& (x, v)) = terrain.el(& neighbor_idx) { + if (x == b'S' || x == b'a') && (elev == b'a' || elev == b'b') { + res = node.cost + 1; + done = true; + break; + } + if !v && (x > elev || elev - x <= 1) { + unvisited.push(Node::new(neighbor_idx.clone(), node.cost + 1)); + } + } + } + terrain[idx].1 = true; + } + if done { break; } + } + + println!("{}", res); +} |