AtCoder Beginner Contest 460 D

https://atcoder.jp/contests/abc460/tasks/abc460_d

1回目以降に黒になったマスは白と黒が交互に現れるので、最初に黒になるターンをメモしておきます。

// Repeatedly Repainting
#![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 {
    S: Vec<Vec<bool>>       // trueなら黒
}

impl Table {
    fn H(&self) -> usize {
        self.S.len()
    }
    
    fn W(&self) -> usize {
        self.S[0].len()
    }
    
    fn is_black(&self, (x, y): Point) -> bool {
        self.S[x][y]
    }
    
    fn neighbors(&self, (x, y): Point) -> Vec<Point> {
        let mut neighs = vec![];
        for dx in 0..3 {
            let x1 = x + dx;
            if x1 == 0 || x1 == self.H() + 1 {
                continue
            }
            for dy in 0..3 {
                if dx == 1 && dy == 1 {
                    continue
                }
                let y1 = y + dy;
                if y1 == 0 || y1 == self.W() + 1 {
                    continue
                }
                neighs.push((x1 - 1, y1 - 1))
            }
        }
        neighs
    }
    
    fn read() -> Table {
        let v: Vec<usize> = read_vec();
        let H = v[0];
        let S: Vec<Vec<bool>> = (0..H).
                                map(|_| read::<String>().chars().
                                        map(|c| c == '#').collect()).
                                collect();
        Table { S }
    }
}


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

use std::collections::VecDeque;

fn print_results(turns: Vec<Vec<i32>>) {
    for v in turns {
        let s: String = v.into_iter().
                        map(|n| if n % 2 == 0 { '#' } else { '.' }).
                        collect();
        println!("{}", s)
    }
}

fn F(table: Table) {
    // はじめて黒になったターン
    let mut turns: Vec<Vec<i32>> = vec![vec![-1; table.W()]; table.H()];
    
    let mut init_black_points = vec![];
    for x in 0..table.H() {
        for y in 0..table.W() {
            if table.is_black((x, y)) {
                turns[x][y] = 0;
                init_black_points.push((x, y))
            }
        }
    }
    
    let mut q: VecDeque<Point> = VecDeque::new();
    for &pt in init_black_points.iter() {
        for (x, y) in table.neighbors(pt) {
            if turns[x][y] == -1 {
                turns[x][y] = 1;
                q.push_back((x, y));
            }
        }
    }
    
    // 初期黒はいったん-1に戻す
    for (x, y) in init_black_points {
        turns[x][y] = -1
    }
    
    while let Some(pt) = q.pop_front() {
        let turn = turns[pt.0][pt.1];
        for (x, y) in table.neighbors(pt) {
            if turns[x][y] == -1 {
                turns[x][y] = turn + 1;
                q.push_back((x, y));
            }
        }
    }
    
    print_results(turns)
}

fn main() {
    let table = Table::read();
    F(table)
}