結果

問題 No.179 塗り分け
ユーザー はむ吉🐹
提出日時 2016-03-04 21:55:49
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,548 bytes
コンパイル時間 284 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 16,640 KB
最終ジャッジ日時 2024-10-03 03:15:37
合計ジャッジ時間 8,978 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 6 TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
import itertools


IS_RED = 1
IS_BLUE = 2


def solve(height, width, black_cells):
    num_black_cells = len(black_cells)
    if num_black_cells == 0:
        return False
    elif num_black_cells % 2 == 1:
        return False
    deltas = [(0, dc) for dc in range(1, width)]
    prod = itertools.product(range(1, height), range(-width + 1, width))
    deltas += [(dr, dc) for dr, dc in prod]
    for dr, dc in deltas:
        counter = 0
        painted = [array.array("B", (0 for _ in range(width)))
                   for _ in range(height)]
        for r0, c0 in black_cells:
            if counter >= num_black_cells:
                return True
            (r, c) = (r0 + dr, c0 + dc)
            if r < 0 or r >= height or c < 0 or c >= width:
                if not painted[r0][c0]:
                    break
            elif painted[r0][c0] == 0 and painted[r][c] == 0:
                if (r, c) not in black_cells:
                    break
                painted[r0][c0] = IS_RED
                painted[r][c] = IS_BLUE
                counter += 2
        else:
            return True
    else:
        return False


def main():
    h, w = map(int, input().split())
    black_cells = []
    for r in range(h):
        for c, cell in enumerate(input()):
            if cell == "#":
                black_cells.append((r, c))
    black_cells.sort()
    if solve(h, w, black_cells):
        print("YES")
    else:
        print("NO")


if __name__ == '__main__':
    main()
0