結果
問題 | No.179 塗り分け |
ユーザー |
|
提出日時 | 2020-02-25 21:57:11 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 94 ms / 3,000 ms |
コード長 | 1,174 bytes |
コンパイル時間 | 439 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-07-23 15:11:52 |
合計ジャッジ時間 | 3,196 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 40 |
ソースコード
import sys from itertools import product H, W = map(int, input().split()) S = [input() for _ in range(H)] def solve(h0, w0, dh, dw): color = [[None] * W for _ in range(H)] color[h0][w0] = 'R' color[h0 + dh][w0 + dw] = 'B' for h, w in product(range(h0, H), range(W)): if h == h0 and w <= w0: continue if S[h][w] == '#' and color[h][w] == None: if h + dh < H and w + dw < W and S[h + dh][ w + dw] == '#' and color[h + dh][w + dw] == None: color[h][w] = 'R' color[h + dh][w + dw] = 'B' else: return False for h, w in product(range(H), range(W)): if S[h][w] == '#' and color[h][w] == None: return False return True h0 = w0 = -1 for h, w in product(range(H), range(W)): if S[h][w] == '#': h0, w0 = h, w break else: print('NO') sys.exit() yes = False for h, w in product(range(h0, H), range(W)): if h == h0 and w <= w0: continue if S[h][w] == '#': dh, dw = h - h0, w - w0 if (solve(h0, w0, dh, dw)): yes = True break print('YES' if yes else 'NO')