139 lines
3.4 KiB
Rust
139 lines
3.4 KiB
Rust
use std::{
|
|
collections::VecDeque,
|
|
io::{read_to_string, stdin},
|
|
};
|
|
|
|
enum Tile {
|
|
Wall,
|
|
Blank,
|
|
}
|
|
|
|
#[derive(Clone, Copy, PartialEq)]
|
|
enum Dir {
|
|
East,
|
|
West,
|
|
South,
|
|
North,
|
|
}
|
|
|
|
impl Dir {
|
|
fn convert_from_no(x: isize) -> Dir {
|
|
match x {
|
|
1 => Dir::East,
|
|
2 => Dir::West,
|
|
3 => Dir::South,
|
|
4 => Dir::North,
|
|
_ => Dir::North,
|
|
}
|
|
}
|
|
|
|
fn convert_to_no(d: Dir) -> usize {
|
|
match d {
|
|
Dir::East => 0,
|
|
Dir::West => 1,
|
|
Dir::South => 2,
|
|
Dir::North => 3,
|
|
}
|
|
}
|
|
|
|
fn turn_right(d: Dir) -> Dir {
|
|
match d {
|
|
Dir::East => Dir::South,
|
|
Dir::West => Dir::North,
|
|
Dir::North => Dir::East,
|
|
Dir::South => Dir::West,
|
|
}
|
|
}
|
|
|
|
fn turn_left(d: Dir) -> Dir {
|
|
match d {
|
|
Dir::East => Dir::North,
|
|
Dir::West => Dir::South,
|
|
Dir::North => Dir::West,
|
|
Dir::South => Dir::East,
|
|
}
|
|
}
|
|
|
|
fn dir_vec(d: Dir) -> (isize, isize) {
|
|
match d {
|
|
Dir::East => (0, 1),
|
|
Dir::West => (0, -1),
|
|
Dir::North => (-1, 0),
|
|
Dir::South => (1, 0),
|
|
}
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
let temp = read_to_string(stdin()).unwrap();
|
|
let mut iter = temp
|
|
.split_ascii_whitespace()
|
|
.map(|x| x.parse::<isize>().unwrap());
|
|
let (m, n) = (iter.next().unwrap(), iter.next().unwrap());
|
|
|
|
let field: Vec<Vec<Tile>> = (0..m)
|
|
.map(|_| {
|
|
(0..n)
|
|
.map(|_| match iter.next().unwrap() {
|
|
0 => Tile::Blank,
|
|
_ => Tile::Wall,
|
|
})
|
|
.collect()
|
|
})
|
|
.collect();
|
|
|
|
let is_in = |r: isize, c: isize| r >= 0 && r < m && c >= 0 && c < n;
|
|
|
|
let start_state = (
|
|
iter.next().unwrap() - 1,
|
|
iter.next().unwrap() - 1,
|
|
Dir::convert_from_no(iter.next().unwrap()),
|
|
);
|
|
|
|
let dest_state = (
|
|
iter.next().unwrap() - 1,
|
|
iter.next().unwrap() - 1,
|
|
Dir::convert_from_no(iter.next().unwrap()),
|
|
);
|
|
|
|
let mut deq = VecDeque::new();
|
|
let mut vis: Vec<Vec<Vec<_>>> = (0..m)
|
|
.map(|_| (0..n).map(|_| (0..4).map(|_| false).collect()).collect())
|
|
.collect();
|
|
deq.push_back((start_state, 0));
|
|
|
|
while deq.len() > 0 {
|
|
let ((curr_r, curr_c, curr_d), curr_act) = deq.pop_front().unwrap();
|
|
|
|
if vis[curr_r as usize][curr_c as usize][Dir::convert_to_no(curr_d)] {
|
|
continue;
|
|
} else {
|
|
vis[curr_r as usize][curr_c as usize][Dir::convert_to_no(curr_d)] = true;
|
|
}
|
|
|
|
if curr_r == dest_state.0 && curr_c == dest_state.1 && curr_d == dest_state.2 {
|
|
println!("{}", curr_act);
|
|
break;
|
|
}
|
|
let dirv = Dir::dir_vec(curr_d);
|
|
|
|
let mut check_r = curr_r;
|
|
let mut check_c = curr_c;
|
|
|
|
for _ in 0..3 {
|
|
check_r += dirv.0;
|
|
check_c += dirv.1;
|
|
if is_in(check_r, check_c)
|
|
&& matches!(field[check_r as usize][check_c as usize], Tile::Blank)
|
|
{
|
|
deq.push_back(((check_r, check_c, curr_d), curr_act + 1));
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
|
|
deq.push_back(((curr_r, curr_c, Dir::turn_left(curr_d)), curr_act + 1));
|
|
deq.push_back(((curr_r, curr_c, Dir::turn_right(curr_d)), curr_act + 1));
|
|
}
|
|
}
|