結果

問題 No.179 塗り分け
コンテスト
ユーザー utrhira
提出日時 2018-07-10 00:53:01
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,582 bytes
コンパイル時間 73 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 17,824 KB
最終ジャッジ日時 2024-07-18 05:12:43
合計ジャッジ時間 5,239 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

def d(rt, lt):
    return (rt[0] - lt[0], rt[1] - lt[1])

def x(t):
    return t[0]

def y(t):
    return t[1]

def cond(right, left):

    rx = sorted(sorted(right, key=x), key=y)
    lx = sorted(sorted(left, key=x), key=y)

    diff = d(lx[0], rx[0])
    rset = {(rrx[0] + diff[0], rrx[1] + diff[1]) for rrx in rx}
    lset = {llx for llx in lx}
    return rset == lset

def debug(h, w, right, left, cellz):
    nn = [["." for _ in range(w)] for _ in range(h)]
    for h,w in right:
        nn[h][w] = "@"
    for h,w in left:
        nn[h][w] = "%"
    for nx in nn:
        print("".join(nx))
    print("-----")

if __name__ == "__main__":
    s = input()
    h, w = [int(i) for i in s.split(" ")]
    
    cellz = []
    for hi in range(h):
        s = input()
        for wi, ch in enumerate(s):
            if ch == "#":
                cellz.append((hi, wi))
    
    if len(cellz) % 2 == 1:
        print("NO")
    else:
        maxcell = len(cellz)
        grpsize = maxcell // 2
    
        def func(cand, s, e):
            if len(cand) == grpsize:
                right = [ cellz[i] for i in range(maxcell) if i in cand]
                left = [ cellz[i] for i in range(maxcell) if i not in cand]
                #debug(h, w, right, left, cellz)
                return cond(right, left)
            else:
                for i in range(s, e+1):
                    if func(cand + [i], i + 1, e + 1):
                        return True
                return False
    
        if func([], 0, grpsize):
            print("YES")
        else:
            print("NO")
0