AtCoder Beginner Contest 326 D

https://atcoder.jp/contests/abc326/tasks/abc326_d

左上からABC.を当てはめていき、その時点でおかしくなければ次へ進みます。そうでなければ次の文字を、文字がなくなったら前に戻ります。

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


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

struct Board {
    cells: Vec<Vec<char>>,
    R: String,
    C: String
}

impl Board {
    fn new(R: String, C: String) -> Board {
        let N = R.len();
        let cells: Vec<Vec<char>> = (0..N).map(|_| vec!['.'; N]).collect();
        Board { cells, R, C }
    }
    
    fn len(&self) -> usize {
        self.R.len()
    }
    
    fn is_valid_row(&self, i: usize, j: usize) -> bool {
        let mut s = HashSet::new();
        for j1 in 0..j+1 {
            let c = self.cells[i][j1];
            if c == '.' {
                continue
            }
            if s.contains(&c) {
                return false
            }
            s.insert(c);
        }
        if self.len() - j <= 3 - s.len() {
            return false
        }
        
        for i1 in 0..i {
            if self.cells[i1][j] != '.' {
                return true
            }
        }
        
        let c1 = self.cells[i][j];
        c1 == '.' || c1 == self.C.chars().nth(j).unwrap()
    }
    
    fn is_valid_column(&self, i: usize, j: usize) -> bool {
        let mut s = HashSet::new();
        for i1 in 0..i+1 {
            let c = self.cells[i1][j];
            if c == '.' {
                continue
            }
            if s.contains(&c) {
                return false
            }
            s.insert(c);
        }
        if self.len() - i <= 3 - s.len() {
            return false
        }
        
        for j1 in 0..j {
            if self.cells[i][j1] != '.' {
                return true
            }
        }
        
        let c1 = self.cells[i][j];
        c1 == '.' || c1 == self.R.chars().nth(i).unwrap()
    }
    
    fn is_valid(&self, i: usize, j: usize) -> bool {
        self.is_valid_row(i, j) && self.is_valid_column(i, j)
    }
    
    fn next_cell(&self, i: usize, j: usize) -> Option<(usize, usize)> {
        if i == self.len() - 1 && j == self.len() - 1 {
            None
        }
        else if j == self.len() - 1 {
            Some((i + 1, 0))
        }
        else {
            Some((i, j + 1))
        }
    }
    
    fn solve(&mut self, i: usize, j: usize) -> bool {
        let abc = vec!['A', 'B', 'C', '.'];
        for c in abc.into_iter() {
            self.cells[i][j] = c;
            if !self.is_valid(i, j) {
                continue
            }
            
            match self.next_cell(i, j) {
                None           => return true,
                Some((i1, j1)) => {
                    let b = self.solve(i1, j1);
                    if b {
                        return true
                    }
                }
            }
        }
        false
    }
    
    fn print(&self) {
        for v in self.cells.iter() {
            println!("{}", v.iter().map(|&c| c).collect::<String>())
        }
    }
}


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

fn read_input() -> (String, String) {
    let _N: usize = read();
    let R = read();
    let C = read();
    (R, C)
}

fn F(R: String, C: String) {
    let mut board = Board::new(R, C);
    if board.solve(0, 0) {
        println!("Yes");
        board.print()
    }
    else {
        println!("No")
    }
}

fn main() {
    let (R, C) = read_input();
    F(R, C)
}