AtCoder Beginner Contest 317 E

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))
}