https://atcoder.jp/contests/abc322/tasks/abc322_d
回転とシフトするだけなので、しらみつぶしでも計算量は微小です。
charのテーブルを使いましたが、2進数を使った方がたぶん簡単でしたね。
// Polyomino #![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 YesNo(b: bool) -> String { return if b { "Yes".to_string() } else { "No".to_string() } } //////////////////// Polyomino //////////////////// struct Polyomino { P: [[char; 4]; 4] } impl Polyomino { fn count(&self) -> usize { (0..16).filter(|&i| self.P[i/4][i%4] == '#').count() } fn is_overlapped(&self, other: &Polyomino) -> bool { (0..4).any(|y| (0..4).any(|x| self.P[y][x] == '#' && other.P[y][x] == '#')) } fn add(&self, other: &Polyomino) -> Polyomino { let mut P: [[char; 4]; 4] = [['.'; 4]; 4]; for y in 0..4 { for x in 0..4 { let b = self.P[y][x] == '#' || other.P[y][x] == '#'; P[y][x] = if b { '#' } else { '.' } } } Polyomino { P } } fn is_shiftable(&self, dx: i32, dy: i32) -> bool { if dx < 0 { if (0..-dx).any(|x| (0..4).any(|y| self.P[y][x as usize] == '#')) { return false } } else if dx > 0 { if (4-dx..4).any(|x| (0..4).any(|y| self.P[y][x as usize] == '#')) { return false } } if dy < 0 { if (0..-dy).any(|y| (0..4).any(|x| self.P[y as usize][x] == '#')) { return false } } else if dy > 0 { if (4-dy..4).any(|y| (0..4).any(|x| self.P[y as usize][x] == '#')) { return false } } true } fn shift(&self, dx: i32, dy: i32) -> Polyomino { let mut P: [[char; 4]; 4] = [['.'; 4]; 4]; for y in 0..4 { let y1 = y + dy; if y1 < 0 || 4 <= y1 { continue } for x in 0..4 { let x1 = x + dx; if x1 < 0 || 4 <= x1 { continue } P[y1 as usize][x1 as usize] = self.P[y as usize][x as usize] } } Polyomino { P } } fn rotate(&self, angle: i32) -> Polyomino { let mut P: [[char; 4]; 4] = [['.'; 4]; 4]; for y in 0..4 { for x in 0..4 { if angle == 0 { P[y][x] = self.P[y][x] } else if angle == 90 { P[y][x] = self.P[x][3-y] } else if angle == 180 { P[y][x] = self.P[3-y][3-x] } else { P[y][x] = self.P[3-x][y] } } } Polyomino { P } } fn read() -> Polyomino { let mut P: [[char; 4]; 4] = [['.'; 4]; 4]; for i in 0..4 { let s: String = read(); for (j, c) in s.chars().enumerate() { P[i][j] = c } } Polyomino { P } } } //////////////////// process //////////////////// fn read_input() -> Vec<Polyomino> { (0..3).map(|_| Polyomino::read()).collect::<Vec<_>>() } fn fill(P: Polyomino, Ps: &[Polyomino]) -> bool { if Ps.is_empty() { return true } for angle in (0..360).step_by(90) { let P1 = Ps[0].rotate(angle); for dy in -3..4 { for dx in -3..4 { if P1.is_shiftable(dx, dy) { let P2 = P1.shift(dx, dy); if !P.is_overlapped(&P2) && fill(P.add(&P2), &Ps[1..]) { return true } } } } } false } fn F(Ps: Vec<Polyomino>) -> bool { if Ps.iter().map(|p| p.count()).sum::<usize>() != 16 { return false } for dy in -3..4 { for dx in -3..4 { if Ps[0].is_shiftable(dx, dy) { let P2 = Ps[0].shift(dx, dy); if fill(P2, &Ps[1..]) { return true } } } } false } fn main() { let Ps = read_input(); println!("{}", YesNo(F(Ps))) }