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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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);
}
|
