[プログラマー]ロックとキー

問題の説明

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

フルナビゲーション->アレイを展開

回転90:アレイ90度回転

check:拡張ロックの中間部が1であるかどうかを確認します.
挿入キー

、キー

を抜く.

# key의 회전 함수(시계방향)
def rotate90(mat):
    length = len(mat)
    ret = [[0] * length for _ in range(length)]

    for r in range(length):
        for c in range(length):
            ret[c][length - 1 - r] = mat[r][c]
            
    return ret

# key의 행렬과 lock의 행렬 체크 함수
def check(lock, n, m): # lock, len(lock), len(key)
    for i in range(n): # lock 길이만큼 반복
        for j in range(n):
            if lock[n + i][n + j] != 1: # 해당 범위내에 있는 값이 1이 아니면 False
                return False
    return True
    
def solution(key, lock):
    # lock의 0부분을 key의 1로 채우기
    # lock의 1과 key의 1이 만나면 안됨
    n, m = len(lock), len(key)
    
    # lock(자물쇠)의 크기를 3배 확장
    new_lock = [[0] * (n * 3) for _ in range(n * 3)] # [n * 3][n * 3]
    
    # 중앙에 기존 자물쇠 대입
    for i in range(n):
        for j in range(n):
            new_lock[n + i][n + j] = lock[i][j]
            
    for _ in range(4): # 4방향 확인
        key = rotate90(key) # key 회전
        
        for x in range(2 * n):
            for y in range(2 * n):
                
                # 열쇠 끼워 넣기
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + j] += key[i][j]
                        
                if check(new_lock, n, m): # 자물쇠로 열 수 있는 경우 True 반환
                    return True
            
                # 열쇠 다시 빼기
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + j] -= key[i][j]
                        
    return False

lock配列を拡張するだけなら...解けると思った.
アレイ回転とcheck関数を実現したが.
回転から始め、ロックを繰り返し移動します.
ロックを移動し、回転を繰り返します.
しかし、拡張が思い出せないので、解決できません.
これは本当に復習の要求だ.
最初は白駿3190。蛇。題とあまり差がありませんでしたか?でも.
配列された値を加えると,照合の論理のみが似ている.