Lv 3ロックとキー

質問する

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

結合はMxM(3≦M≦20,Mは自然数)サイズの二次元配列である.

ロックは、NxN(3≦N≦20、Nは自然数)サイズの2次元配列である.

Mは常にNより小さい.

キーとlockの要素は0または1で構成されます.

0は「主」部分、1は「回転」部分を表します.

I/O例
keylockresult[[0, 0, 0], [1, 0, 0], [0, 1, 1]][[1, 1, 1], [1, 1, 0], [1, 0, 1]]true
I/O例説明

keyを時計回りに90度回転させ、右に1つのセルを移動させ、下に1つのセルを移動させることで、lockのすべてのメイン部分を正確に埋めることができます.

に答える

回転後、BFSでナビゲーションを行います.

コード#コード#

def rotate_right(m):
    new_m = [[0]*len(m) for _ in range(len(m))]
    for i in range(len(m)):
        for j in range(len(m)):
            new_m[j][len(m)-i-1] = m[i][j]
    return new_m
    
def rotate_left(m):
    new_m = [[0]*len(m) for _ in range(len(m))]
    for i in range(len(m)):
        for j in range(len(m)):
            new_m[len(m)-1-j][i] = m[i][j]
    return new_m

def one_eighty(m):
    new_m = [[0]*len(m) for _ in range(len(m))]
    for i in range(len(m)):
        for j in range(len(m)):
            new_m[len(m)-1-i][len(m)-1-j] = m[i][j]
    return new_m

def assemble(M,m,lock):
    for k in range(len(lock)):
        for l in range(len(lock)):
            if M[k+m][l+m] + lock[k][l] != 1:
                return False
    return True

def solution(key, lock):
    keys = [key,rotate_left(key),one_eighty(key),rotate_right(key)]
    m = len(key)-1
    ml = m * 2 + len(lock)
    for key in keys:
        for i in range(m + len(lock)):
            for j in range(m + len(lock)):
                M = [[0]*ml for _ in range(ml)]
                for k in range(len(key)):
                    for l in range(len(key)):
                        M[k+i][l+j] = key[k][l]
                if assemble(M,m,lock):
                    return True
    return False