結果

問題 No.179 塗り分け
ユーザー gew1fw
提出日時 2025-06-12 20:37:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 537 ms / 3,000 ms
コード長 1,547 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,272 KB
実行使用メモリ 77,424 KB
最終ジャッジ日時 2025-06-12 20:38:07
合計ジャッジ時間 7,173 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import product

def main():
    H, W = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(H)]
    
    B = set()
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                B.add((i, j))
    
    if len(B) < 2:
        print("NO")
        return
    
    vectors = set()
    for (x1, y1) in B:
        for (x2, y2) in B:
            dx = x2 - x1
            dy = y2 - y1
            if dx == 0 and dy == 0:
                continue
            vectors.add((dx, dy))
    
    for (dx, dy) in vectors:
        if len(B) % 2 != 0:
            continue
        
        visited = set()
        valid = True
        for (x, y) in B:
            if (x, y) in visited:
                continue
            
            if (x + dx, y + dy) in B:
                if (x + dx, y + dy) in visited:
                    valid = False
                    break
                visited.add((x, y))
                visited.add((x + dx, y + dy))
            else:
                if (x - dx, y - dy) in B:
                    if (x - dx, y - dy) in visited:
                        valid = False
                        break
                    visited.add((x, y))
                    visited.add((x - dx, y - dy))
                else:
                    valid = False
                    break
        
        if valid and len(visited) == len(B):
            print("YES")
            return
    
    print("NO")

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