AtCoder Beginner Contest 405 D

https://atcoder.jp/contests/abc405/tasks/abc405_d

Eから幅優先探索するだけですね。

// Escape Route
#![allow(non_snake_case)]


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


//////////////////// Maze ////////////////////

type Point = (usize, usize);

struct Maze {
    H: usize,
    W: usize,
    cells: Vec<Vec<char>>,
    dirs: Vec<Vec<char>>,
    dists: Vec<Vec<i32>>
}

impl Maze {
    fn find_end_point(&self) -> Vec<Point> {
        let mut pts: Vec<Point> = vec![];
        for x in 0..self.H {
            for y in 0..self.W {
                if self.cells[x][y] == 'E' {
                    pts.push((x, y))
                }
            }
        }
        pts
    }
    
    fn neighbors(&self, pt: Point) -> Vec<Point> {
        let (x, y) = pt;
        let mut pts: Vec<Point> = vec![];
        if x > 0 && self.cells[x-1][y] == '.' {
            pts.push((x-1, y))
        }
        if x < self.H - 1 && self.cells[x+1][y] == '.' {
            pts.push((x+1, y))
        }
        if y > 0 && self.cells[x][y-1] == '.' {
            pts.push((x, y-1))
        }
        if y < self.W - 1 && self.cells[x][y+1] == '.' {
            pts.push((x, y+1))
        }
        pts
    }
    
    fn is_arrived(&self, (x, y): Point) -> bool {
        self.dists[x][y] != i32::MAX
    }
    
    fn get_dist(&self, (x, y): Point) -> i32 {
        self.dists[x][y]
    }
    
    fn set_dist(&mut self, d: i32, (x, y): Point) {
        self.dists[x][y] = d
    }
    
    fn set_dirs(&mut self, (x1, y1): Point, (x0, y0): Point) {
        if y1 > y0 {
            self.dirs[x1][y1] = '<'
        }
        else if y1 < y0 {
            self.dirs[x1][y1] = '>'
        }
        else if x1 > x0 {
            self.dirs[x1][y1] = '^'
        }
        else {
            self.dirs[x1][y1] = 'v'
        }
    }
    
    fn print(&self) {
        for v in self.dirs.iter() {
            println!("{}", v.iter().collect::<String>())
        }
    }
    
    fn read() -> Maze {
        let v: Vec<usize> = read_vec();
        let (H, W) = (v[0], v[1]);
        let cells: Vec<Vec<char>> =
                    (0..H).map(|_| read::<String>().chars().collect()).collect();
        let dirs = cells.clone();
        let dists: Vec<Vec<i32>> = vec![vec![i32::MAX; W]; H];
        Maze { H, W, cells, dirs, dists }
    }
}


//////////////////// process ////////////////////

use std::collections::VecDeque;

fn F(mut maze: Maze) {
    let pts_end = maze.find_end_point();
    let mut q: VecDeque<Point> = VecDeque::new();
    for pt_end in pts_end.into_iter() {
        maze.set_dist(0, pt_end);
        q.push_back(pt_end);
    }
    while let Some(pt1) = q.pop_front() {
        let d1 = maze.get_dist(pt1);
        for pt2 in maze.neighbors(pt1).into_iter() {
            if !maze.is_arrived(pt2) {
                maze.set_dist(d1 + 1, pt2);
                q.push_back(pt2);
                maze.set_dirs(pt2, pt1)
            }
        }
    }
    maze.print()
}

fn main() {
    let maze = Maze::read();
    F(maze)
}