AtCoder Beginner Contest 400 D

https://atcoder.jp/contests/abc400/tasks/abc400_d

グラフとか考えずに、ふつうにDijkstraっぽくやればいいですね。ただし、距離は0か1進むので、BinaryHeapではなく、VecDequeを用意して、距離0なら前に、距離1なら後ろにpushすればよいです。

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


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

type Point = (usize, usize);
type Dist = i32;
type Node = usize;

struct Table {
    H: usize,
    W: usize,
    data: Vec<Vec<char>>,
    dist: Vec<Dist>
}

impl Table {
    fn encode(&self, x: usize, y: usize) -> Node {
        x * self.W + y
    }
    
    fn decode(&self, i: Node) -> Point {
        (i / self.W, i % self.W)
    }
    
    fn is_road(&self, i: usize) -> bool {
        let (x, y) = self.decode(i);
        self.data[x][y] == '.'
    }
    
    fn is_wall(&self, i: usize) -> bool {
        let (x, y) = self.decode(i);
        self.data[x][y] == '#'
    }
    
    fn is_visited(&self, i: usize) -> bool {
        self.dist[i] != Dist::MAX
    }
    
    fn neighbors(&self, i: usize) -> Vec<usize> {
        let (x0, y0) = self.decode(i);
        let mut neighs: Vec<usize> = vec![];
        if x0 > 0 {
            neighs.push(self.encode(x0 - 1, y0))
        }
        if x0 + 1 < self.H {
            neighs.push(self.encode(x0 + 1, y0))
        }
        if y0 > 0 {
            neighs.push(self.encode(x0, y0 - 1))
        }
        if y0 + 1 < self.W {
            neighs.push(self.encode(x0, y0 + 1))
        }
        neighs
    }
    
    fn create(S: Vec<String>) -> Table {
        let H = S.len();
        let W = S[0].len();
        let data: Vec<Vec<char>> = S.into_iter().
                                    map(|s| s.chars().collect::<Vec<_>>()).
                                    collect();
        let dist: Vec<Dist> = vec![Dist::MAX; H*W];
        Table { H, W, data, dist }
    }
}


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

fn read_input() -> (Vec<String>, usize, usize, usize, usize) {
    let v: Vec<usize> = read_vec();
    let H = v[0];
    let S: Vec<String> = (0..H).map(|_| read()).collect();
    let w: Vec<usize> = read_vec();
    let (A, B, C, D) = (w[0]-1, w[1]-1, w[2]-1, w[3]-1);
    (S, A, B, C, D)
}

// 隣の隣
fn neighbor_neighbor(v0: Node, v1: Node, table: &Table) -> Option<Node> {
    let (x0, y0) = table.decode(v0);
    let (x1, y1) = table.decode(v1);
    if x0 == x1 {
        if y1 * 2 < y0 {
            return None
        }
        let y2 = y1 * 2 - y0;
        if y2 >= table.W {
            None
        }
        else {
            Some(table.encode(x0, y2))
        }
    }
    else {  // yは同じ前提
        if x1 * 2 < x0 {
            return None
        }
        let x2 = x1 * 2 - x0;
        if x2 >= table.H {
            None
        }
        else {
            Some(table.encode(x2, y0))
        }
    }
}

use std::collections::VecDeque;

fn F(S: Vec<String>, A: usize, B: usize, C: usize, D: usize) -> i32 {
    let mut table = Table::create(S);
    
    let mut deq = VecDeque::new();
    let start = table.encode(A, B);
    let goal = table.encode(C, D);
    deq.push_back((start, 0));
    while let Some((v0, d)) = deq.pop_front() {
        if v0 == goal {
            return d
        }
        else if table.is_visited(v0) {
            continue
        }
        table.dist[v0] = d;
        
        for v1 in table.neighbors(v0) {
            if table.is_visited(v1) {
                continue
            }
            else if table.is_road(v1) {
                deq.push_front((v1, d));
            }
            else {
                deq.push_back((v1, d + 1));
                if let Some(v2) = neighbor_neighbor(v0, v1, &table) {
                    deq.push_back((v2, d + 1));
                }
            }
        }
    }
    0
}

fn main() {
    let (S, A, B, C, D) = read_input();
    println!("{}", F(S, A, B, C, D))
}