https://atcoder.jp/contests/abc317/tasks/abc317_e
題意通りに"!"を付けて、Queueを使って最短距離を得ます。
// Avoid Eye Contact #![allow(non_snake_case)] use std::ops::Add; use std::collections::VecDeque; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>().split_whitespace() .map(|e| e.parse().ok().unwrap()).collect() } //////////////////// Point //////////////////// #[derive(Clone, Copy, Eq, PartialEq)] struct Point { x: i64, y: i64, } impl Add for Point { type Output = Self; fn add(self, other: Self) -> Self { Self { x: self.x + other.x, y: self.y + other.y } } } impl Point { fn new(x: i64, y: i64) -> Point { Point { x, y } } } //////////////////// Field //////////////////// struct Field { A: Vec<Vec<char>> } impl Field { fn H(&self) -> usize { self.A.len() } fn W(&self) -> usize { self.A[0].len() } fn cell(&self, pt: &Point) -> char { self.A[pt.y as usize][pt.x as usize] } fn is_inner(&self, pt: &Point) -> bool { 0 <= pt.x && pt.x < (self.W() as i64) && 0 <= pt.y && pt.y < (self.H() as i64) } fn get_dir(&self, pt: &Point) -> Point { match self.cell(pt) { '>' => Point::new(1, 0), '<' => Point::new(-1, 0), '^' => Point::new(0, -1), 'v' => Point::new(0, 1), _ => Point::new(0, 0) } } fn is_overlooking(&self, pt: &Point) -> bool { self.is_inner(pt) && (self.cell(pt) == '.' || self.cell(pt) == '!') } fn is_reachable(&self, pt: &Point) -> bool { self.is_inner(pt) && (self.cell(pt) == '.' || self.cell(pt) == 'G') } fn set_overlooking(&mut self, pt: &Point) { self.A[pt.y as usize][pt.x as usize] = '!' } fn overlook(&mut self, mut pt: Point) { let dir = self.get_dir(&pt); if dir.x == 0 && dir.y == 0 { return } loop { pt = pt + dir; if self.is_overlooking(&pt) { self.set_overlooking(&pt) } else { break } } } fn mark_observable(&mut self) { for y in 0..self.H() { for x in 0..self.W() { let pt = Point::new(x as i64, y as i64); self.overlook(pt) } } } fn find_start(&self) -> Point { for (y, v) in self.A.iter().enumerate() { for (x, c) in v.iter().enumerate() { if *c == 'S' { return Point { x: x as i64, y: y as i64 } } } } Point { x: 0, y: 0 } } fn find_goal(&self) -> Point { for (y, v) in self.A.iter().enumerate() { for (x, c) in v.iter().enumerate() { if *c == 'G' { return Point { x: x as i64, y: y as i64 } } } } Point { x: 0, y: 0 } } fn get_neighbors(&self, pt0: &Point) -> Vec<Point> { let dirs: Vec<Point> = vec![Point::new(1, 0), Point::new(0, -1), Point::new(0, 1), Point::new(-1, 0)]; dirs.into_iter().map(|dir| *pt0 + dir). filter(|pt| self.is_reachable(&pt)). collect::<Vec<Point>>() } fn solve(&self) -> i32 { let mut visited: Vec<Vec<bool>> = vec![vec![false; self.W()]; self.H()]; let start = self.find_start(); let goal = self.find_goal(); let mut q: VecDeque<(Point, i32)> = VecDeque::new(); q.push_back((start, 0)); visited[start.y as usize][start.x as usize] = true; while let Some((pt0, d)) = q.pop_front() { if pt0 == goal { return d } for pt in self.get_neighbors(&pt0).into_iter() { if !visited[pt.y as usize][pt.x as usize] { q.push_back((pt, d+1)); visited[pt.y as usize][pt.x as usize] = true } } } -1 } fn read() -> Field { let v = read_vec(); let H: usize = v[0]; let A: Vec<Vec<char>> = (0..H).map(|_| read::<String>()). map(|s| s.chars().collect::<Vec<char>>()). collect(); Field { A } } } //////////////////// process //////////////////// fn f(mut field: Field) -> i32 { field.mark_observable(); field.solve() } fn main() { let field = Field::read(); println!("{}", f(field)) }