[プログラマー]鍵と鍵(Python)

問題の説明

考古学者の「救命圏」は古代遺跡で秘密の扉を発見し、宝物や遺跡がたくさんあると推測した.ドアを開けてみると、ドアが特殊な形の鍵でロックされていて、ドアの前に紙があり、特殊な形の鍵でロックを解除する方法が書かれています.
ロックされたロックは、メッシュサイズが1 x 1のN x Nサイズの正方形メッシュであり、特殊な形状のキーはM x Mサイズの正方形メッシュである.
鍵には溝があり、鍵にも溝と突起があります.鍵は回転と移動が可能な構造で、鍵の回転部分が鍵の溝部分とぴったり合っていると鍵が開きます.ロック領域以外の鍵の溝と突起はロック解除に影響しないが、ロック領域内では鍵の突起とロックの溝が完全に一致し、鍵の突起とロックの突起にぶつかることができない必要がある.また、ロックのすべての溝を埋めなければなりません.そうすれば、ロックを解除できます.
パラメータにキーを表す2 D配列キーとロックを表す2 D配列ロックが与えられた場合、true(キーがロックを解除できる場合)とfalse(ロックを解除できない場合)を返すソルバを完了します.

せいげんじょうけん

keyはMxM(3≦M≦20,Mは自然数)サイズの二次元配列である.
lockは,NxN(3≦N≦20,Nは自然数)サイズの二次元配列である.
Mは常にNより小さい.
keyとlockの要素は0または1で構成されています.
0はメイン(Main)セクション、1は回転(Rotation)セクションを表します.

I/O例

keylockresult[[0, 0, 0], [1, 0, 0], [0, 1, 1]][[1, 1, 1], [1, 1, 0], [1, 0, 1]]true

に答える

グリッドが左側にあり、キーが右側にある場合

空のメッシュを選択し、メッシュに対してキーリングを選択し、90度回転するたびにキーリングが領域に入っていることを確認します.
キー突起が溝であるが、キーの他の突起が非溝に存在する場合は、それを除外します.

def solution(key, lock):
    n, m=len(lock),len(key)
    key_li= [ [] for _ in range(4) ]
    count_key=0
    for r in range(m):
        for c in range(m):
            if key[r][c]==1:
                count_key+=1
                for i in range(4):
                    key_li[i].append([r,c])
                    t = r
                    r = c
                    c = n-t-1
    lock_li=[]
    count_lock=0
    for i in range(n):
        for j in range(n):
            if lock[i][j]==0:
                count_lock+=1
                lock_li.append([i,j])
    if count_lock==0:
        return True
    
    if count_lock > count_key:
        return False
    else:
        for i in range(count_lock):
            for j in range(4):
                for k in range(count_key):
                    li = []
                    x = lock_li[i][0]-key_li[j][k][0]
                    y = lock_li[i][1]-key_li[j][k][1]
                    for g in range(count_key):
                        li.append([key_li[j][g][0]+x, key_li[j][g][1]+y])
                    t=True
                    for lo in lock_li:
                        if lo not in li:
                            t=False
                            break
                        li.remove(lo)
                    for trash in li:
                        if 0 <= trash[0] < n and 0 <= trash[1] < n:
                            t=False
                    if t:
                        return True
        if t==False:
            return False