AtCoder Beginner Contest 431 E

https://atcoder.jp/contests/abc431/tasks/abc431_e

BinaryHeapを使って、何回鏡を変えたかの小さいほうから処理して、ゴールにたどり着いたときの操作回数を得ます。

// Reflection on Grid
#![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()
}


//////////////////// Dir ////////////////////

#[derive(Ord, PartialOrd, Eq, PartialEq, Clone)]
enum Dir {
    Up,
    Down,
    Left,
    Right
}

impl Dir {
    fn index(&self) -> usize {
        match self {
            Dir::Up    => 0,
            Dir::Down  => 1,
            Dir::Left  => 2,
            Dir::Right => 3
        }
    }
}


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

type Point = (usize, usize);
type Dist = i64;

const INF: i32 = 1_000_000_000;

struct Table {
    H: usize,
    W: usize,
    cells: Vec<Vec<(Dist, [i32; 4])>>
}

impl Table {
    fn original_mirror(&self, pt: Point) -> Dist {
        let (x, y) = pt;
        self.cells[x][y].0
    }
    
    fn is_goal(&self, pt: Point) -> bool {
        pt == (self.H - 1, self.W)
    }
    
    fn reflect(dir: Dir, mirror: Dist) -> Dir {
        if mirror == 0 {
            dir
        }
        else if mirror == 1 {
            match dir {
                Dir::Up    => Dir::Left,
                Dir::Down  => Dir::Right,
                Dir::Left  => Dir::Up,
                Dir::Right => Dir::Down
            }
        }
        else {
            match dir {
                Dir::Up    => Dir::Right,
                Dir::Down  => Dir::Left,
                Dir::Left  => Dir::Down,
                Dir::Right => Dir::Up
            }
        }
    }
    
    fn leaves(&self, pt: Point, dir: Dir) -> bool {
        let (x, y) = pt;
        match dir {
            Dir::Up    => x == 0,
            Dir::Down  => x == self.H - 1,
            Dir::Left  => y == 0,
            Dir::Right => if x == self.H - 1 { false } else { y == self.W - 1 }
        }
    }
    
    fn next(&self, pt: Point, dir: Dir, mirror: Dist) -> Option<(Point, Dir)> {
        let (x, y) = pt;
        let new_dir = Table::reflect(dir, mirror);
        if self.leaves(pt, new_dir.clone()) {
            return None
        }
        match new_dir {
            Dir::Up    => Some(((x-1, y), new_dir)),
            Dir::Down  => Some(((x+1, y), new_dir)),
            Dir::Left  => Some(((x, y-1), new_dir)),
            Dir::Right => Some(((x, y+1), new_dir))
        }
    }
    
    fn put(&mut self, num: i32, pt: Point, dir: Dir) -> bool {
        let (x, y) = pt;
        let b = self.cells[x][y].1[dir.index()] == INF;
        if b {
            self.cells[x][y].1[dir.index()] = num
        }
        b
    }
    
    fn to_mirror(c: char) -> Dist {
        match c {
            'A' => 0,
            'B' => 1,
            _   => 2
        }
    }
    
    fn read() -> Table {
        let v: Vec<usize> = read_vec();
        let (H, W) = (v[0], v[1]);
        let cells: Vec<Vec<(Dist, [i32; 4])>> =
                    (0..H).map(|_| read::<String>().
                                    chars().
                                    map(|c| (Table::to_mirror(c), [INF; 4])).
                                    collect::<Vec<(Dist, [i32; 4])>>()).
                    collect();
        Table { H, W, cells }
    }
}


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

use std::collections::BinaryHeap;

fn F_each(mut table: Table) -> i32 {
    let mut heap: BinaryHeap<(i32, Point, Dir)> = BinaryHeap::new();
    heap.push((0, (0, 0), Dir::Right)); // (num changes, x, y, dir)
    while let Some((num_, pt0, dir0)) = heap.pop() {
        let num0 = -num_;
        if table.is_goal(pt0) {
            return num0
        }
        else if !table.put(num0, pt0, dir0.clone()) {
            continue
        }
        
        for mirror in 0..3 {
            if let Some((pt, dir)) = table.next(pt0, dir0.clone(), mirror) {
                let new_num = num0 +
                    (if mirror == table.original_mirror(pt0) { 0 } else { 1 });
                heap.push((-new_num, pt, dir))
            }
        }
    }
    return -1
}

fn F(T: usize) {
    for _ in 0..T {
        let table = Table::read();
        println!("{}", F_each(table))
    }
}

fn main() {
    let T: usize = read();
    F(T)
}