AtCoder Beginner Contest 420 D

https://atcoder.jp/contests/abc420/tasks/abc420_d

マスごとにドアが元通りと反対になっているときの最小の操作数を記録すればよいです。

// Substr Swap
#![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()
}


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

type Point = (usize, usize);

struct Maze {
    A: Vec<Vec<char>>
}

impl Maze {
    fn H(&self) -> usize { self.A.len() }
    fn W(&self) -> usize { self.A[0].len() }
    
    fn is_reachable(&self, pt: Point, turn: bool) -> bool {
        let c = self.A[pt.0][pt.1];
        !(c == '#' || (!turn && c == 'x') || (turn && c == 'o'))
    }
    
    fn is_switch(&self, pt: Point) -> bool {
        self.A[pt.0][pt.1] == '?'
    }
    
    fn find_start(&self) -> Point {
        for x in 0..self.H() {
            for y in 0..self.W() {
                if self.A[x][y] == 'S' {
                    return (x, y)
                }
            }
        }
        (0, 0)  // ここには来ないはず
    }
    
    fn is_goal(&self, pt: Point) -> bool {
        self.A[pt.0][pt.1] == 'G'
    }
    
    fn neighbors(&self, pt: Point, turn: bool) -> Vec<Point> {
        let mut neighs: Vec<Point> = vec![];
        if pt.0 > 0 && self.is_reachable((pt.0-1, pt.1), turn) {
            neighs.push((pt.0-1, pt.1))
        }
        if pt.0 < self.H()-1 && self.is_reachable((pt.0+1, pt.1), turn) {
            neighs.push((pt.0+1, pt.1))
        }
        if pt.1 > 0 && self.is_reachable((pt.0, pt.1-1), turn) {
            neighs.push((pt.0, pt.1-1))
        }
        if pt.1 < self.W()-1 && self.is_reachable((pt.0, pt.1+1), turn) {
            neighs.push((pt.0, pt.1+1))
        }
        neighs
    }
    
    fn read() -> Maze {
        let v: Vec<usize> = read_vec();
        let H = v[0];
        let mut A: Vec<Vec<char>> = vec![vec![]; H];
        for i in 0..H {
            A[i] = read::<String>().chars().collect()
        }
        Maze { A }
    }
}


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

fn F(maze: Maze) -> i32 {
    let mut table: Vec<Vec<[i32; 2]>> =
                vec![vec![[i32::MAX, i32::MAX]; maze.W()]; maze.H()];
    let mut q: VecDeque<(Point, bool, i32)> = VecDeque::new();
    let pt_start = maze.find_start();
    q.push_back((pt_start, false, 0));
    table[pt_start.0][pt_start.1][0] = 0;
    while let Some((pt, mut turn, dist)) = q.pop_front() {
        if maze.is_goal(pt) {
            return dist
        }
        else if maze.is_switch(pt) {
            turn = !turn
        }
        
        let neighs = maze.neighbors(pt, turn);
        for pt1 in neighs {
            if table[pt1.0][pt1.1][if turn { 1 } else { 0 }] == i32::MAX {
                q.push_back((pt1, turn, dist + 1));
                table[pt1.0][pt1.1][if turn { 1 } else { 0 }] = dist + 1
            }
        }
    }
    -1
}

fn main() {
    let maze = Maze::read();
    println!("{}", F(maze))
}