AtCoder Beginner Contest 322 D

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