AtCoder Beginner Contest 413 F

https://atcoder.jp/contests/abc413/tasks/abc413_f

ゴールからはじめて先入れ先出しすればよいです。取り出したグリッドの隣を見てその隣が2つ以上最小移動回数が確定で、小さいほうから2つ目が取り出したグリッド+1なら、最小移動回数が決まります。

// No Passage
#![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);

struct Table {
    a: Vec<Vec<i64>>
}

impl Table {
    fn H(&self) -> usize {
        self.a.len()
    }
    
    fn W(&self) -> usize {
        self.a[0].len()
    }
    
    fn get(&self, pt: Point) -> i64 {
        self.a[pt.0][pt.1]
    }
    
    fn get_neighbor_values(&self, pt: Point) -> Vec<i64> {
        self.neighbors(pt).into_iter().filter(|&pt1| self.is_visited(pt1)).
                                map(|pt1| self.get(pt1)).collect::<Vec<i64>>()
    }
    
    fn set(&mut self, pt: Point, value: i64) {
        self.a[pt.0][pt.1] = value
    }
    
    fn is_visited(&self, pt: Point) -> bool {
        self.a[pt.0][pt.1] >= 0
    }
    
    fn neighbors(&self, pt: Point) -> Vec<Point> {
        let mut neis: Vec<Point> = vec![];
        if pt.0 > 0 {
            neis.push((pt.0 - 1, pt.1))
        }
        if pt.0 < self.H() - 1 {
            neis.push((pt.0 + 1, pt.1))
        }
        if pt.1 > 0 {
            neis.push((pt.0, pt.1 - 1))
        }
        if pt.1 < self.W() - 1 {
            neis.push((pt.0, pt.1 + 1))
        }
        neis
    }
    
    fn read() -> Table {
        let v: Vec<usize> = read_vec();
        let (H, W, K) = (v[0], v[1], v[2]);
        let mut a: Vec<Vec<i64>> = vec![vec![-1; W]; H];
        for _ in 0..K {
            let w: Vec<usize> = read_vec();
            let (R, C) = (w[0] - 1, w[1] - 1);
            a[R][C] = 0
        }
        Table { a }
    }
}


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

use std::collections::VecDeque;

fn F(mut table: Table) -> i64 {
    let mut q: VecDeque<Point> = (0..table.H()).
                            flat_map(|x| (0..table.W()).map(move |y| (x, y))).
                            filter(|&pt| table.is_visited(pt)).
                            collect();
    while let Some(pt) = q.pop_front() {
        for pt1 in table.neighbors(pt) {
            if table.is_visited(pt1) {
                continue
            }
            let mut values = table.get_neighbor_values(pt1);
            if values.len() < 2 {
                continue
            }
            values.sort();
            let value = values[1];
            if value != table.get(pt) {
                continue
            }
            table.set(pt1, value + 1);
            q.push_back(pt1)
        }
    }
    
    (0..table.H()).flat_map(|x| (0..table.W()).map(move |y| (x, y))).
                            filter(|&pt| table.is_visited(pt)).
                            map(|pt| table.get(pt)).sum::<i64>()
}

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