[コードテスト]2020 KAKAO BLIND RECRUITMENTロックとキーwith Python

問題の説明

考古学者の「救命圏」は古代遺跡で秘密の扉を発見し、宝物や遺跡がたくさんあると推測した.ドアを開けてみると、ドアが特殊な形の鍵でロックされていて、ドアの前に紙があり、特殊な形の鍵でロックを解除する方法が書かれています.
ロックされたロックは、メッシュサイズが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は「回転」を表します.

に答える

フィールドフォーマットの質問に久しぶりに答えます.問題を読み始めたばかりの頃は、効率を高めるために多くの事項を適用すべきだと思っていましたが、制限事項から見ると、そうする必要はないと思い、最も簡単な方法でコードを書きました.

solution(key,lock)solution(key, lock)solution(key,lock)

def solution(key, lock):
    for key in appendRotateCase(key): 
        if isMatch(key,lock):
            return True
    return False

抽象優先定義が好きなので、まだ定義されていない関数を宣言しました.appendRotateCase()appendRotateCase()関数を使用して回転時のキーを生成して追加し、isMatchisMatchisMatch関数を使用してロックを解除できるかどうかを検証します.では、この2つの関数を正しく定義すれば、問題を解決することができます.

appendRotateCase(key)appendRotateCase(key)appendRotateCase(key)

appendRotateCase()appendRotateCase()関数では、最も簡単な方法が使用されています.90度回転は列を行として使用することに相当するため、2つの繰り返し文を使用して位置を再割り当てする方法が使用されます.ここで効率を考慮すると、疎行列が使用されます.(でも…ちょっと面倒くさい…)

def appendRotateCase(key):
    size=len(key)
    ret=[key]
    for i in range(3):
        rotate=[[] for _ in range(size)]
        for r in range(size):
            for c in range(size):
                rotate[c].append(ret[-1][size-1-r][c])
        ret.append(rotate)
    return ret

isMatch(key,lock)isMatch(key,lock)isMatch(key,lock)

isMatch関数は1つの関数であり,大きな側面から2つの行列が重なり,ロック部分がいずれも1であることを決定した.2∮llen(key)∮llen(key)−2∮lle(lock)2∮llen(key)∮2+len(lock)サイズの大きなフィールドを中央に配置し,ロックを移動して比較することで関数を実現した.効率を重視すれば、鍵を一段ずつ全部移動するよりも、鍵部分と重なる箇所だけを再配分します.

def isMatch(key,lock):
    fieldSize=2*len(key)-2+len(lock)
    field=[[0]*fieldSize for _ in range(fieldSize) ]
    reviseField(field,lock,len(key)-1,len(key)-1)
    for row in range(fieldSize-len(key)+1):
        for col in range(fieldSize-len(key)+1):
            reviseField(field,key,row,col)
            isComplete=True
            for r in range(len(key)-1,len(key)-1+len(lock)):
                for c in range(len(key)-1,len(key)-1+len(lock)):
                    if field[r][c]!=1:
                        isComplete=False
                        break
            if isComplete:
                return True
            reviseField(field,key,row,col,remove=True)
    return False
 
 def reviseField(field,matrix,row,col,remove=False):
    for r in range(row,row+len(matrix)):
        for c in range(col,col+len(matrix)):
            if remove:
                field[r][c]-=matrix[r-row][c-col]
            else:
                field[r][c]+=matrix[r-row][c-col]