結果

問題 No.179 塗り分け
コンテスト
ユーザー gemmaro
提出日時 2020-11-05 11:38:59
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 19 ms / 3,000 ms
コード長 2,579 bytes
コンパイル時間 13,348 ms
コンパイル使用メモリ 388,736 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-23 15:22:00
合計ジャッジ時間 13,970 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::{convert::TryInto, io::stdin};

fn main() {
    let (h, w) = {
        let mut buf = String::new();
        stdin().read_line(&mut buf).unwrap();
        let mut h_and_w = buf.split_whitespace().map(|s| s.parse::<u8>().unwrap());

        (h_and_w.next().unwrap(), h_and_w.next().unwrap())
    };

    let ss: Vec<Vec<Square>> = {
        (1..=h)
            .map(|_i| {
                let mut buf = String::new();
                stdin().read_line(&mut buf).unwrap();

                buf.trim_end().chars().map(|c| c.into()).collect()
            })
            .collect()
    };

    println!("{}", solve(h, w, ss));
}

fn solve(h: u8, w: u8, ss: Vec<Vec<Square>>) -> &'static str {
    if !all_white(&ss) && any_overlap(h, w, ss) {
        "YES"
    } else {
        "NO"
    }
}

fn any_overlap(h: u8, w: u8, ss: Vec<Vec<Square>>) -> bool {
    for vec_row in 0..(h as i8) {
        for vec_col in (-(w as i8) + 1)..(w as i8) {
            if is_overlap(vec_row, vec_col, h, w, ss.clone()) {
                return true;
            }
        }
    }

    false
}

fn is_overlap(vec_row: i8, vec_col: i8, h: u8, w: u8, ss: Vec<Vec<Square>>) -> bool {
    if vec_row == 0 && vec_col == 0 {
        return false;
    }

    let mut ss = ss;

    for src_row in 0..h {
        for src_col in 0..w {
            let src_row = src_row as usize;
            let src_col = src_col as usize;

            if let Square::Black = ss[src_row][src_col] {
                let dst_row = (src_row as i8) + vec_row;
                let dst_col = (src_col as i8) + vec_col;

                if !in_rect(dst_row, dst_col, h, w) {
                    return false;
                }

                let dst_row = dst_row as usize;
                let dst_col = dst_col as usize;

                if let Square::Black = ss[dst_row][dst_col] {
                    ss[src_row][src_col] = Square::White;
                    ss[dst_row][dst_col] = Square::White;
                }
            }
        }
    }

    all_white(&ss)
}

fn in_rect(row: i8, col: i8, h: u8, w: u8) -> bool {
    row >= 0 && row <= (h - 1).try_into().unwrap() && col >= 0 && col <= (w - 1).try_into().unwrap()
}

fn all_white(ss: &[Vec<Square>]) -> bool {
    ss.iter()
        .all(|row| row.iter().all(|&col| col == Square::White))
}

#[derive(PartialEq, Copy, Clone, Debug)]
enum Square {
    White,
    Black,
}

impl From<char> for Square {
    fn from(c: char) -> Self {
        match c {
            '#' => Self::Black,
            '.' => Self::White,
            _ => unreachable!(),
        }
    }
}
0