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
|
use std::collections::VecDeque;
#[derive(Copy, Clone)]
pub struct Cell {
pub h: i8,
#[allow(unused)]
pub is_start: bool,
pub seen: usize
}
pub struct Map {
pub cells: Vec<Vec<Cell>>,
pub end: (usize, usize)
}
impl Map {
pub fn neighbors(&self, v: (usize, usize)) -> Vec<(usize, usize)> {
[
((v.0 as i64) -1, v.1 as i64),
((v.0 as i64) +1, v.1 as i64),
(v.0 as i64, (v.1 as i64) -1),
(v.0 as i64, (v.1 as i64) +1)
].iter()
.filter(|p| p.0 >= 0 && p.0 < self.cells.len() as i64 &&
p.1 >= 0 && p.1 < self.cells[0].len() as i64)
.map(|x| (x.0 as usize, x.1 as usize))
.collect()
}
}
pub fn read_input() -> Map {
let mut cells = Vec::<Vec<Cell>>::new();
let mut end = (0, 0);
let mut line = String::new();
while std::io::stdin().read_line(&mut line).unwrap() > 0 {
let mut v = Vec::<Cell>::new();
let cs = line.as_bytes();
for i in 0..line.len()-1 {
let mut is_start = false;
let h = match cs[i] as char {
'a'..='z' => cs[i] - ('a' as u8),
'S' => { is_start = true; 0 },
'E' => { end = (cells.len(), i); 26 },
u => panic!("Unexpected char {}", u)
} as i8;
let seen = if cs[i] as char == 'E' { 0 } else { usize::MAX };
v.push(Cell { h, is_start, seen });
}
cells.push(v);
line.clear();
}
Map { cells, end }
}
pub fn shortest_path_back(map: &mut Map, end: fn(&Cell) -> bool) -> usize {
let mut next = VecDeque::from([map.end]);
while !next.is_empty() {
let i = next.pop_front().unwrap();
let v = map.cells[i.0][i.1];
for j in map.neighbors(i) {
let w = &mut map.cells[j.0][j.1];
if w.h - v.h >= -1 && w.seen == usize::MAX {
w.seen = v.seen + 1;
if end(w) { return w.seen; }
next.push_back(j);
}
}
}
panic!("No path found");
}
|
