結果

問題 No.179 塗り分け
コンテスト
ユーザー utrhira
提出日時 2018-07-10 00:11:03
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,297 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 70 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 16,256 KB
最終ジャッジ日時 2024-07-18 01:47:13
合計ジャッジ時間 7,891 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4 WA * 2
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def cond(right, left):
    rx = sorted(right, key=lambda ax:ax[0]^2 + ax[1]^2)
    lx = sorted(left, key=lambda ax:ax[0]^2 + ax[1]^2)
    
    rhead, *rrest = rx
    lhead, *lrest = lx

    diff = (rhead[0] - lhead[0], rhead[1] - lhead[1])
    for rr in rrest:
        rrd = (rr[0] + diff[0], rr[1] + diff[1])
        if not rrd in lrest:
            return False
    return True

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]
                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