AtCoder Beginner Contest 345 D

https://atcoder.jp/contests/abc345/tasks/abc345_d

しらみつぶしで十分間に合います。次に長方形を置く場所を決めるとき、必ず左上から左に空いているマスを探します。

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

fn YesNo(b: bool) -> String {
    return if b { "Yes" } else { "No" }.to_string()
}


//////////////////// Table ////////////////////

type Rectangle = (usize, usize);
type Position = (usize, usize);

fn read_rect() -> Rectangle {
    let v = read_vec();
    let (A, B) = (v[0], v[1]);
    (A, B)
}

fn rotate(rect: &Rectangle) -> Rectangle {
    (rect.1, rect.0)
}

struct Table {
    table: Vec<Vec<bool>>
}

impl Table {
    fn new(H: usize, W: usize) -> Table {
        let table = vec![vec![false; W]; H];
        Table { table }
    }
    
    fn is_filled(&self) -> bool {
        for v in self.table.iter() {
            for b in v.iter() {
                if !b {
                    return false
                }
            }
        }
        true
    }
    
    fn start_position(&self) -> Position {
        for (i, v) in self.table.iter().enumerate() {
            for (j, b) in v.iter().enumerate() {
                if !b {
                    return (i, j)
                }
            }
        }
        (0, 0)  // dummy
    }
    
    fn is_placable(&self, rect: &Rectangle, pos: Position) -> bool {
        if rect.0 + pos.0 > self.table.len() ||
                    rect.1 + pos.1 > self.table[0].len() {
            return false
        }
        
        for i in 0..rect.0 {
            for j in 0..rect.1 {
                if self.table[i+pos.0][j+pos.1] {
                    return false
                }
            }
        }
        true
    }
    
    fn place(&mut self, rect: &Rectangle, pos: Position) {
        for i in 0..rect.0 {
            for j in 0..rect.1 {
                self.table[i+pos.0][j+pos.1] = true
            }
        }
    }
    
    fn remove(&mut self, rect: &Rectangle, pos: Position) {
        for i in 0..rect.0 {
            for j in 0..rect.1 {
                self.table[i+pos.0][j+pos.1] = false
            }
        }
    }
}


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

fn read_input() -> (usize, usize, Vec<Rectangle>) {
    let v = read_vec();
    let (N, H, W) = (v[0], v[1], v[2]);
    let rects: Vec<Rectangle> = (0..N).map(|_| read_rect()).collect();
    (H, W, rects)
}

fn F_core(rects: &Vec<Rectangle>, table: &mut Table) -> bool {
    if table.is_filled() {
        return true
    }
    
    let pos = table.start_position();
    for (i, rect) in rects.iter().enumerate() {
        let new_rects = rects.iter().enumerate().filter(|&(j, _)| j != i).
                                        map(|(_, &r)| r).collect::<Vec<_>>();
        if table.is_placable(rect, pos) {
            table.place(rect, pos);
            if F_core(&new_rects, table) {
                return true
            }
            else {
                table.remove(rect, pos)
            }
        }
        let rot_rect = rotate(rect);
        if table.is_placable(&rot_rect, pos) {
            table.place(&rot_rect, pos);
            if F_core(&new_rects, table) {
                return true
            }
            else {
                table.remove(&rot_rect, pos)
            }
        }
    }
    false
}

fn F(H: usize, W: usize, rects: Vec<Rectangle>) -> bool {
    let mut table = Table::new(H, W);
    F_core(&rects, &mut table)
}

fn main() {
    let (H, W, rects) = read_input();
    println!("{}", YesNo(F(H, W, rects)))
}