結果

問題 No.179 塗り分け
ユーザー YoshihitoYoshihito
提出日時 2020-09-18 17:06:33
言語 Rust
(1.77.0)
結果
AC  
実行時間 17 ms / 3,000 ms
コード長 5,506 bytes
コンパイル時間 2,908 ms
コンパイル使用メモリ 151,968 KB
実行使用メモリ 4,388 KB
最終ジャッジ日時 2023-09-30 21:34:04
合計ジャッジ時間 4,522 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 1 ms
4,380 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 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 14 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 1 ms
4,384 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,376 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 6 ms
4,380 KB
testcase_22 AC 17 ms
4,376 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 2 ms
4,380 KB
testcase_25 AC 1 ms
4,380 KB
testcase_26 AC 2 ms
4,384 KB
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 1 ms
4,380 KB
testcase_29 AC 1 ms
4,380 KB
testcase_30 AC 1 ms
4,380 KB
testcase_31 AC 1 ms
4,380 KB
testcase_32 AC 1 ms
4,380 KB
testcase_33 AC 2 ms
4,388 KB
testcase_34 AC 1 ms
4,380 KB
testcase_35 AC 1 ms
4,376 KB
testcase_36 AC 1 ms
4,380 KB
testcase_37 AC 1 ms
4,380 KB
testcase_38 AC 1 ms
4,380 KB
testcase_39 AC 1 ms
4,380 KB
testcase_40 AC 1 ms
4,380 KB
testcase_41 AC 1 ms
4,380 KB
testcase_42 AC 1 ms
4,380 KB
testcase_43 AC 1 ms
4,380 KB
testcase_44 AC 1 ms
4,380 KB
testcase_45 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::{self, Read};

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

impl Color {
    fn abbrev(&self) -> char {
        match *self {
            Color::White => '.',
            Color::Black => '#',
            Color::Red => 'R',
            Color::Blue => 'B',
        }
    }

    fn is_replaceable(&self) -> bool {
        match *self {
            Color::Black => true,
            _ => false
        }
    }
}

impl From<char> for Color {
    fn from(c: char) -> Self {
        match c {
            '#' => Color::Black,
            '.' => Color::White,
            _ => panic!("unknown color: {}", c),
        }
    }
}

#[derive(Debug, Clone)]
struct Board {
    w: i32,
    h: i32,
    cells: Vec<Color>,
}

impl Board {
    fn new(w: i32, h: i32, cells: Vec<Color>) -> Board {
        Board { w, h, cells }
    }

    fn width(&self) -> i32 {
        self.w
    }

    fn height(&self) -> i32 {
        self.h
    }

    #[allow(unused)]
    fn show(&self) {
        for r in 0..self.h {
            let start = self.index_of(r, 0).unwrap();
            let row = self
                .cells
                .iter()
                .skip(start)
                .take(self.w as usize)
                .map(|c| c.abbrev())
                .collect::<String>();

            println!("{}", row);
        }
    }

    fn can_paint(&self) -> bool {
        self.cells.iter().any(|&c| c.is_replaceable())
    }

    fn index_of(&self, r: i32, c: i32) -> Option<usize> {
        if r < 0 || r >= self.h {
            None
        } else if c < 0 || c >= self.w {
            None
        } else {
            Some(((r * self.w) + c) as usize)
        }
    }

    fn is_replaceable(&self, r: i32, c: i32) -> bool {
        self.index_of(r, c)
            .map(|index| self.cells[index] == Color::Black)
            .unwrap_or(false)
    }

    fn replace(&mut self, r: i32, c: i32, color: Color) {
        assert!(self.is_replaceable(r, c));
        if let Some(index) = self.index_of(r, c) {
            self.cells[index] = color;
        }
    }

    fn reset_with(&mut self, other: &Board) {
        self.cells.clear();
        self.cells.extend_from_slice(&other.cells);
    }
}

impl From<Input> for Board {
    fn from(input: Input) -> Self {
        Board::new(input.w, input.h, input.cells)
    }
}

struct BoardPainter {
    original: Board,
    painted: Board,
}

impl BoardPainter {
    fn new(original: Board) -> BoardPainter {
        let painted = original.clone();
        BoardPainter { original, painted }
    }

    fn try_paint_with_distance(&mut self, dist_r: i32, dist_c: i32) -> bool {
        if !self.original.can_paint() {
            return false
        }

        let h = self.painted.height();
        let w = self.painted.width();

        let target = &mut self.painted;
        target.reset_with(&self.original);

        for r in 0..h {
            for c in 0..w {
                if !target.is_replaceable(r, c) {
                    // 赤色に塗れないマスの場合は次のマスに移動する
                    continue;
                }

                let blue_r = r + dist_r; // 行はY軸の移動距離
                let blue_c = c + dist_c; // 列はX軸の移動距離
                if !target.is_replaceable(blue_r, blue_c) {
                    // 置き換え失敗
                    // println!("## fail: d=({}, {}), red=({}, {}), blue=({}, {})", dist_r, dist_c, r, c, blue_r, blue_c);
                    return false
                }

                // 赤・青どちらも置き換えできる
                target.replace(r, c, Color::Red);
                target.replace(blue_r, blue_c, Color::Blue);
            }
        }

        // 塗り分け成功！
        true
    }
}

#[derive(Debug)]
struct Input {
    h: i32,
    w: i32,
    cells: Vec<Color>,
}

fn next_token(cin_lock: &mut io::StdinLock) -> String {
    cin_lock
        .by_ref()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>()
}

fn read_input(cin_lock: &mut io::StdinLock) -> Input {
    let h: usize = next_token(cin_lock).parse().unwrap();
    let w: usize = next_token(cin_lock).parse().unwrap();

    let mut cells = Vec::with_capacity(h * w);
    (0..h).for_each(|_| {
        let s = next_token(cin_lock);
        cells.extend(s.chars().take(w).map(Color::from));
    });

    Input { h: h as i32, w: w as i32, cells }
}

fn solve(input: Input, _cin_lock: &mut io::StdinLock) {
    let b = Board::from(input);
    // b.show();

    let h = b.height();
    let w = b.width();
    let mut painter = BoardPainter::new(b);

    let mut found = false;
    for r in 0..h {
        for c in 0..w {
            if r == 0 && c == 0 {
                continue;
            }

            found = found || painter.try_paint_with_distance(r, c);
            found = found || painter.try_paint_with_distance(r * -1, c);
            found = found || painter.try_paint_with_distance(r, c * -1);
            found = found || painter.try_paint_with_distance(r * -1, c * -1);
            if found {
                break;
            }
        }
    }

    let answer = if found { "YES" } else { "NO" };
    println!("{}", answer);
}

fn main() {
    let cin = io::stdin();
    let mut cin_lock = cin.lock();
    let input = read_input(&mut cin_lock);
    solve(input, &mut cin_lock);
}
0