[プログラマー]ロックとキー
11466 ワード
問題の説明
考古学者の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)セクションを表します.
![](https://s1.md5.ltd/image/80784efc8895cb3f7a958ade961b574c.png)
![](https://s1.md5.ltd/image/c1c0515bfbcb43f79c49dfebe29fbf42.png)
挿入キー
# 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。蛇。題とあまり差がありませんでしたか?でも.
配列された値を加えると,照合の論理のみが似ている.
Reference
この問題について([プログラマー]ロックとキー), 我々は、より多くの情報をここで見つけました https://velog.io/@ayoung0073/programmers-kakao-자물쇠와열쇠テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol