https://atcoder.jp/contests/abc345/tasks/abc345_d
しらみつぶしで十分間に合います。次に長方形を置く場所を決めるとき、必ず左上から左に空いているマスを探します。
#![allow(non_snake_case)]
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()
}
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)
}
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
}
}
}
}
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)))
}
