結果

問題 No.179 塗り分け
ユーザー gemmarogemmaro
提出日時 2020-11-05 11:38:59
言語 Rust
(1.77.0)
結果
AC  
実行時間 18 ms / 3,000 ms
コード長 2,579 bytes
コンパイル時間 1,293 ms
コンパイル使用メモリ 151,136 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-30 21:34:46
合計ジャッジ時間 3,256 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 18 ms
4,380 KB
testcase_09 AC 17 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 12 ms
4,380 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 12 ms
4,380 KB
testcase_21 AC 17 ms
4,376 KB
testcase_22 AC 17 ms
4,380 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 14 ms
4,376 KB
testcase_25 AC 1 ms
4,380 KB
testcase_26 AC 3 ms
4,376 KB
testcase_27 AC 17 ms
4,376 KB
testcase_28 AC 2 ms
4,380 KB
testcase_29 AC 16 ms
4,376 KB
testcase_30 AC 8 ms
4,380 KB
testcase_31 AC 14 ms
4,380 KB
testcase_32 AC 5 ms
4,376 KB
testcase_33 AC 16 ms
4,376 KB
testcase_34 AC 4 ms
4,380 KB
testcase_35 AC 15 ms
4,376 KB
testcase_36 AC 1 ms
4,380 KB
testcase_37 AC 1 ms
4,384 KB
testcase_38 AC 1 ms
4,376 KB
testcase_39 AC 1 ms
4,376 KB
testcase_40 AC 1 ms
4,380 KB
testcase_41 AC 1 ms
4,376 KB
testcase_42 AC 1 ms
4,376 KB
testcase_43 AC 1 ms
4,376 KB
testcase_44 AC 3 ms
4,380 KB
testcase_45 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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