AtCoder Beginner Contest 425 D

https://atcoder.jp/contests/abc425/tasks/abc425_d

新たに黒く塗ったセルの隣のセルが次に塗れるセルの候補なので、それを集めて塗れるか判定します。

// Ulam-Warburton Automaton
#![allow(non_snake_case)]

use std::collections::HashSet;


//////////////////// 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()
}


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

type Cell = (usize, usize);

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

impl Board {
    fn H(&self) -> usize {
        self.table.len()
    }
    
    fn W(&self) -> usize {
        self.table[0].len()
    }
    
    fn is_black(&self, (x, y): Cell) -> bool {
        self.table[x][y] == '#'
    }
    
    fn neighbors(&self, (x0, y0): Cell) -> Vec<Cell> {
        let mut neis: Vec<Cell> = vec![];
        if x0 > 0 {
            neis.push((x0 - 1, y0))
        }
        if x0 < self.H() - 1 {
            neis.push((x0 + 1, y0))
        }
        if y0 > 0 {
            neis.push((x0, y0 - 1))
        }
        if y0 < self.W() - 1 {
            neis.push((x0, y0 + 1))
        }
        neis
    }
    
    fn collect_neighbors(&self, cells: &Vec<Cell>) -> Vec<Cell> {
        let mut set: HashSet::<Cell> = HashSet::new();
        for &c in cells.iter() {
            set.extend(self.neighbors(c))
        }
        set.into_iter().collect::<Vec<_>>()
    }
    
    fn is_paintable(&self, c0: Cell) -> bool {
        if self.is_black(c0) {
            return false
        }
        let neis = self.neighbors(c0);
        neis.into_iter().
            map(|c| if self.is_black(c) { 1 } else { 0 }).
            sum::<usize>() == 1
    }
    
    fn collect_blacks(&self) -> Vec<Cell> {
        let mut blacks: Vec<Cell> = vec![];
        for x in 0..self.H() {
            for y in 0..self.W() {
                if self.is_black((x, y)) {
                    blacks.push((x, y))
                }
            }
        }
        blacks
    }
    
    fn paint(&mut self, cells: &Vec<Cell>) {
        for &(x, y) in cells.iter() {
            self.table[x][y] = '#'
        }
    }
    
    fn read_row() -> Vec<char> {
        let s: String = read();
        s.chars().collect::<Vec<char>>()
    }
    
    fn read() -> Board {
        let v: Vec<usize> = read_vec();
        let H = v[0];
        let table = (0..H).map(|_| Board::read_row()).collect::<Vec<_>>();
        Board { table }
    }
}


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

fn F(mut board: Board) -> usize {
    let mut cells = board.collect_blacks();
    while !cells.is_empty() {
        let neis = board.collect_neighbors(&cells);
        cells = neis.into_iter().filter(|&c| board.is_paintable(c)).collect();
        board.paint(&cells);
    }
    board.collect_blacks().len()
}

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