AtCoder Beginner Contest 453 D

https://atcoder.jp/contests/abc453/tasks/abc453_d

隣は距離1なのでQueueを使えばよいです。ただし、方向依存なので、マスごとにどの方向から来たかで分けて考えます。そして、それぞれにその前がどこから来たかをメモしておいてtrace backするのを簡単にします。

// Go Straight
#![allow(non_snake_case)]

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

fn YesNo(b: bool) -> String {
    return if b { "Yes" } else { "No" }.to_string()
}


//////////////////// Direction ////////////////////

type Point = (usize, usize);

#[repr(usize)]
#[derive(Debug, Clone, Copy, Eq, PartialEq)]
enum Direction {
    Up    = 0,
    Down  = 1,
    Left  = 2,
    Right = 3,
    Null  = 4,
}

impl Direction {
    fn value(self) -> usize {
        self as usize
    }
    
    fn from_usize(n: usize) -> Option<Self> {
        match n {
            0 => Some(Self::Up),
            1 => Some(Self::Down),
            2 => Some(Self::Left),
            3 => Some(Self::Right),
            _ => Some(Self::Null),
        }
    }
    
    fn to_char(self) -> char {
        match self {
            Self::Up    => 'U',
            Self::Down  => 'D',
            Self::Left  => 'L',
            Self::Right => 'R',
            Self::Null  => '.',
        }
    }
    
    fn vec(self) -> (i32, i32) {
        match self {
            Self::Up    => (-1,  0),
            Self::Down  => ( 1,  0),
            Self::Left  => ( 0, -1),
            Self::Right => ( 0,  1),
            Self::Null  => ( 0,  0),
        }
    }
    
    fn move_to((r, c): Point, dir: Direction) -> Point {
        let (dx, dy) = dir.vec();
        ((r as i32 + dx) as usize, (c as i32 + dy) as usize)
    }
    
    fn back((r, c): Point, dir: Direction) -> Point {
        let (dx, dy) = dir.vec();
        ((r as i32 - dx) as usize, (c as i32 - dy) as usize)
    }
}

type PointDir = (Point, Direction);


//////////////////// Table ////////////////////

struct Table {
    g: Vec<Vec<char>>
}

impl Table {
    fn H(&self) -> usize {
        self.g.len()
    }
    
    fn W(&self) -> usize {
        self.g[0].len()
    }
    
    fn find(&self, c1: char) -> Point {
        for r in 0..self.H() {
            for c in 0..self.W() {
                if self.g[r][c] == c1 {
                    return (r, c)
                }
            }
        }
        (usize::MAX, usize::MAX)
    }
    
    fn find_start(&self) -> Point {
        self.find('S')
    }
    
    fn find_goal(&self) -> Point {
        self.find('G')
    }
    
    fn directions_boundary(&self, r: usize, c: usize) -> usize {
        let mut flags: usize = 0;
        if r != 0 && self.g[r-1][c] != '#' {
            flags |= 1 << Direction::Up.value()
        }
        if r != self.H() - 1 && self.g[r+1][c] != '#'  {
            flags |= 1 << Direction::Down.value()
        }
        if c != 0 && self.g[r][c-1] != '#' {
            flags |= 1 << Direction::Left.value()
        }
        if c != self.W() - 1 && self.g[r][c+1] != '#' {
            flags |= 1 << Direction::Right.value()
        }
        
        flags
    }
    
    fn directions_cell(&self, c1: char, d: Direction) -> usize {
        match c1 {
            'x' => 15 & !(1 << d.value()),
            'o' => 1 << d.value(),
            _   => 15
        }
    }
    
    // そのセルに指定した方向から入ったとき、どちらに行けるのか
    fn directions(&self, ((r, c), d): PointDir) -> usize {
        self.directions_boundary(r, c) & self.directions_cell(self.g[r][c], d)
    }
    
    fn move_to(&self, s0: PointDir, dir: Direction) -> PointDir {
        (Direction::move_to(s0.0, dir), dir)
    }
    
    fn nexts(&self, s0: PointDir) -> Vec<PointDir> {
        let mut v: Vec<PointDir> = vec![];
        let dirs = self.directions(s0);
        for d in 0..4 {
            if ((dirs >> d) & 1) == 1 {
                let dir = Direction::from_usize(d).unwrap();
                v.push(self.move_to(s0, dir))
            }
        }
        v
    }
    
    fn read() -> Table {
        let v: Vec<usize> = read_vec();
        let H = v[0];
        let g: Vec<Vec<char>> = (0..H).map(|_| read::<String>().
                                                chars().collect()).collect();
        Table { g }
    }
}


//////////////////// DP ////////////////////

struct DP {
    // [r][c][来た方向]: その前に向いていた方向
    a: Vec<Vec<[Direction; 4]>>
}

impl DP {
    fn new(H: usize, W: usize, start: Point) -> DP {
        let mut a: Vec<Vec<[Direction; 4]>> =
                        vec![vec![[Direction::Null; 4]; W]; H];
        a[start.0][start.1] = [Direction::Up; 4];
        DP { a }
    }
    
    fn is_visited(&self, ((r, c), d): PointDir) -> bool {
        self.a[r][c][d.value()] != Direction::Null
    }
    
    fn get_value(&self, ((r, c), d): PointDir) -> Direction {
        self.a[r][c][d.value()]
    }
    
    fn set_value(&mut self, ((r, c), d): PointDir, v: Direction) {
        self.a[r][c][d.value()] = v
    }
    
    fn trace_back(&self, (mut pt, mut d): PointDir, start: Point) -> String {
        let mut v: Vec<Direction> = vec![];
        while pt != start {
            v.push(d);
            let pt1 = Direction::back(pt, d);
            d = self.get_value((pt, d));
            pt = pt1
        }
        
        v.into_iter().rev().map(|d| Direction::to_char(d)).collect::<String>()
    }
}


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


fn F(table: Table) -> (bool, String) {
    let start = table.find_start();
    let goal = table.find_goal();
    let mut dp = DP::new(table.H(), table.W(), start);
    // (row, col, dir)
    let mut q: VecDeque<PointDir> = VecDeque::new();
    q.push_back((start, Direction::Up));
    while let Some(s) = q.pop_front() {
        let dir = dp.get_value(s);
        for s1 in table.nexts(s) {
            if dp.is_visited(s1) {
                continue
            }
            
            dp.set_value(s1, s.1);
            q.push_back(s1);
            if s1.0 == goal {
                return (true, dp.trace_back(s1, start))
            }
        }
    }
    (false, "".to_string())
}

fn main() {
    let table = Table::read();
    let (b, s) = F(table);
    println!("{}", YesNo(b));
    if b {
        println!("{}", s)
    }
}