AtCoder Beginner Contest 443 E

https://atcoder.jp/contests/abc443/tasks/abc443_e

上にしか行かないので下からたどり着けるマスかどうか調べます。各列の一番下の壁を持っておきます。

// Climbing Silver
#![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 {
    N: usize,
    cells: Vec<Vec<bool>>,      // 元々空白のマスか
    reachable: Vec<Vec<bool>>,
    lowest_walls: Vec<Option<usize>>
}

impl Table {
    fn nexts_rev(&self, (r, c): Point) -> Vec<Point> {
        if r == self.N - 1 {
            return vec![]
        }
        
        let mut points: Vec<Point> = vec![];
        if c > 0 && self.is_reachable((r+1, c-1)) {
            points.push((r+1, c-1))
        }
        if self.is_reachable((r+1, c)) {
            points.push((r+1, c))
        }
        if c < self.N - 1 && self.is_reachable((r+1, c+1)) {
            points.push((r+1, c+1))
        }
        points
    }
    
    fn is_reachable(&self, (r, c): Point) -> bool {
        self.reachable[r][c]
    }
    
    fn set_reachable(&mut self, (r, c): Point) {
        self.reachable[r][c] = true
    }
    
    fn break_wall(&mut self, (r, c): Point) {
        self.reachable[r][c] = true;
        self.lowest_walls[c] = (0..r).rev().filter(|&c1| !self.cells[r][c1]).
                                                                        next();
    }
    
    fn find_lowest_wall(c: usize, cells: &Vec<Vec<bool>>) -> Option<usize> {
        for r in (0..cells.len()).rev() {
            if !cells[r][c] {
                return Some(r)
            }
        }
        None
    }
    
    fn read() -> Table {
        let v: Vec<usize> = read_vec();
        let (N, C) = (v[0], v[1]-1);
        let cells: Vec<Vec<bool>> = (0..N).map(|_| read::<String>()).
                                map(|S| S.chars().map(|c| c == '.').collect()).
                                collect();
        let mut reachable = vec![vec![false; N]; N];
        reachable[N-1][C] = true;
        let lowest_walls: Vec<Option<usize>> =
                (0..N).map(|c| Table::find_lowest_wall(c, &cells)).collect();
        Table { N, cells, reachable, lowest_walls }
    }
}


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

fn walk(r: usize, c: usize, table: &mut Table) {
    if let Some(r1) = table.lowest_walls[c] {
        if r1 > r && !table.cells[r][c] {
            // この列はもう壁を壊せない
            
        }
        else if !table.nexts_rev((r, c)).is_empty() {
            if r1 == r {
                table.break_wall((r, c))
            }
            else {
                table.set_reachable((r, c))
            }
        }
    }
    else {
        for _ in table.nexts_rev((r, c)) {
            table.set_reachable((r, c))
        }
    }
}

fn F_each(mut table: Table) -> String {
    // (N, C)から斜めに見る
    let N = table.N;
    for R in (0..N-1).rev() {
        for c in 0..N {
            walk(R, c, &mut table)
        }
    }
    let bs: Vec<bool> = (0..N).map(|c| table.is_reachable((0, c))).collect();
    bs.into_iter().map(|b| if b { '1' } else { '0' }).collect::<String>()
}

fn F(T: usize) {
    for _ in 0..T {
        let table = Table::read();
        println!("{}", F_each(table))
    }
}

fn main() {
    let T: usize = read();
    F(T)
}