common.rs (2096B)
1 use std::collections::VecDeque; 2 3 #[derive(Copy, Clone)] 4 pub struct Cell { 5 pub h: i8, 6 #[allow(unused)] 7 pub is_start: bool, 8 pub seen: usize 9 } 10 11 pub struct Map { 12 pub cells: Vec<Vec<Cell>>, 13 pub end: (usize, usize) 14 } 15 16 impl Map { 17 pub fn neighbors(&self, v: (usize, usize)) -> Vec<(usize, usize)> { 18 [ 19 ((v.0 as i64) -1, v.1 as i64), 20 ((v.0 as i64) +1, v.1 as i64), 21 (v.0 as i64, (v.1 as i64) -1), 22 (v.0 as i64, (v.1 as i64) +1) 23 ].iter() 24 .filter(|p| p.0 >= 0 && p.0 < self.cells.len() as i64 && 25 p.1 >= 0 && p.1 < self.cells[0].len() as i64) 26 .map(|x| (x.0 as usize, x.1 as usize)) 27 .collect() 28 } 29 } 30 31 pub fn read_input() -> Map { 32 let mut cells = Vec::<Vec<Cell>>::new(); 33 let mut end = (0, 0); 34 let mut line = String::new(); 35 while std::io::stdin().read_line(&mut line).unwrap() > 0 { 36 let mut v = Vec::<Cell>::new(); 37 let cs = line.as_bytes(); 38 for i in 0..line.len()-1 { 39 let mut is_start = false; 40 let h = match cs[i] as char { 41 'a'..='z' => cs[i] - ('a' as u8), 42 'S' => { is_start = true; 0 }, 43 'E' => { end = (cells.len(), i); 26 }, 44 u => panic!("Unexpected char {}", u) 45 } as i8; 46 let seen = if cs[i] as char == 'E' { 0 } else { usize::MAX }; 47 v.push(Cell { h, is_start, seen }); 48 } 49 cells.push(v); 50 line.clear(); 51 } 52 Map { cells, end } 53 } 54 55 pub fn shortest_path_back(map: &mut Map, end: fn(&Cell) -> bool) -> usize { 56 let mut next = VecDeque::from([map.end]); 57 while !next.is_empty() { 58 let i = next.pop_front().unwrap(); 59 let v = map.cells[i.0][i.1]; 60 for j in map.neighbors(i) { 61 let w = &mut map.cells[j.0][j.1]; 62 if w.h - v.h >= -1 && w.seen == usize::MAX { 63 w.seen = v.seen + 1; 64 if end(w) { return w.seen; } 65 next.push_back(j); 66 } 67 } 68 } 69 panic!("No path found"); 70 }