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