AtCoder Beginner Contest 339 D

https://atcoder.jp/contests/abc339/tasks/abc339_d

二人のプレーヤーの位置を状態としたDPですね。最初、HashMapを使っていたのですが、実行時間ががギリギリで、4次元の配列に直したら速くなりました。

// Synchronized Players
#![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()
}


//////////////////// State ////////////////////

type Position = (usize, usize);
type State = (Position, Position);


//////////////////// Board ////////////////////

#[derive(PartialEq)]
enum PosState {
    Player,
    Vacant,
    Object,
}

struct Board {
    S: Vec<Vec<char>>
}

impl Board {
    fn size(&self) -> usize {
        self.S.len()
    }
    
    fn get_state(&self, pos: Position) -> PosState {
        let (x, y) = pos;
        match self.S[x][y] {
            '#' => PosState::Object,
            'P' => PosState::Player,
            _   => PosState::Vacant,
        }
    }
    
    fn is_vacant(&self, pos: Position) -> bool {
        self.get_state(pos) != PosState::Object
    }
    
    fn next_position(&self, pos: Position) -> Option<Position> {
        let (x, y) = pos;
        let N = self.size();
        if y == N-1 {
            if x == N-1 { None } else { Some((x+1, 0)) }
        }
        else {
            Some((x, y+1))
        }
    }
    
    fn find_player(&self, start_pos: Position) -> Option<Position> {
        let mut pos = start_pos;
        loop {
            match self.get_state(pos) {
                PosState::Player => { return Some(pos) },
                _                => ()
            }
            if let Some(pos1) = self.next_position(pos) {
                pos = pos1
            }
            else {
                break
            }
        }
        None
    }
    
    fn positions(&self) -> State {
        let p1 = self.find_player((0, 0));
        let p2 = self.find_player(self.next_position(p1.unwrap()).unwrap());
        if p1.unwrap() <= p2.unwrap() {
            (p1.unwrap(), p2.unwrap())
        }
        else {
            (p2.unwrap(), p1.unwrap())
        }
    }
    
    fn move_player(&self, p: Position, dir: (i32, i32)) -> Position {
        let (x, y) = p;
        let p1 = match dir {
            (-1, 0) => if x == 0 { p } else { (x-1, y) },
            (1, 0)  => if x == self.size()-1 { p } else { (x+1, y) },
            (0, -1) => if y == 0 { p } else { (x, y-1) },
            _       => if y == self.size()-1 { p } else { (x, y+1) }
        };
        if self.is_vacant(p1) { p1 } else { p }
    }
    
    fn move_players(&self, state: State, dir: (i32, i32)) -> State {
        let p1 = self.move_player(state.0, dir);
        let p2 = self.move_player(state.1, dir);
        (p1, p2)
    }
    
    fn read() -> Board {
        let N: usize = read();
        let S: Vec<Vec<char>> =
                (0..N).map(|_| read::<String>().chars().collect()).collect();
        Board { S }
    }
}


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

type DP = Vec<Vec<Vec<Vec<i32>>>>;
const INF: i32 = 1000000000;

fn get_value(state: State, dp: &DP) -> i32 {
    let ((x1, y1), (x2, y2)) = state;
    dp[x1][y1][x2][y2]
}

fn set_value(state: State, v: i32, dp: &mut DP) {
    let ((x1, y1), (x2, y2)) = state;
    dp[x1][y1][x2][y2] = v
}

fn initialize_DP(state: State, N: usize) -> DP {
    let mut dp: DP = vec![vec![vec![vec![INF; N]; N]; N]; N];
    set_value(state, 0, &mut dp);
    dp
}

fn update_DP(state: State, dp: &mut DP, board: &Board) -> Vec<State> {
    let s = get_value(state, &dp);
    let mut new_states: Vec<State> = vec![];
    let dirs: Vec<(i32, i32)> = vec![(-1, 0), (1, 0), (0, -1), (0, 1)];
    for dir in dirs.into_iter() {
        let state1 = board.move_players(state, dir);
        if get_value(state1, &dp) == INF {
            set_value(state1, s+1, dp);
            new_states.push(state1)
        }
    }
    new_states
}

use std::collections::VecDeque;

fn F(board: Board) -> i32 {
    let init_state = board.positions();
    let mut dp: DP = initialize_DP(init_state, board.size());
    let mut queue = VecDeque::new();
    queue.push_back(init_state);
    while let Some(state) = queue.pop_front() {
        let new_states = update_DP(state, &mut dp, &board);
        for s in new_states.into_iter() {
            queue.push_back(s);
            let (p1, p2) = s;
            if p1 == p2 {
                return get_value(s, &dp)
            }
        }
    }
    -1
}

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