実施-4.鍵と鍵

質問する

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

I/O例

key[[0, 0, 0], [1, 0, 0], [0, 1, 1]]

lock[[1, 1, 1], [1, 1, 0], [1, 0, 1]]

resulttrue

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

インプリメンテーションコード

class Solution {
	
	public static int[][] rotate(int[][] key){
		int n = key.length;
		int m = key[0].length;
		int[][] rtKey = new int[m][n];
		for(int i = 0; i < m ; i++){
			for(int j = 0 ; j < n ; j++){
				rtKey[i][j] = key[n-1-j][i];
			}
		}
		return rtKey;
	}
	
	public static boolean check(int[][] lock, int n){
		for(int i = n; i <2*n; i++){
			for(int j = n; j <2*n; j++){
				if(lock[i][j] != 1) return false;
			}
		}
		return true;
	}
	
    public boolean solution(int[][] key, int[][] lock) {
        int n = lock.length;
		int m = key.length;
		int[][] newLock = new int[3*n][3*n];
		// 새로운 배열에 값 넣기
		for(int i = 0 ; i <n ; i++){
			for(int j = 0 ; j < n; j++){
				newLock[i+n][j+n] = lock[i][j];
			}
		}
		for(int ro = 0; ro < 4; ro++){
			key = rotate(key);
			for(int x = 0 ; x <2*n ;x ++){
				for(int y = 0; y <2*n ; y++){
					// 자물쇠에 열쇠 넣기
					for(int i = 0; i < m; i ++){
						for(int j = 0 ; j < m ; j++){
							newLock[x+i][y+j] += key[i][j];
						}
					}
					if(check(newLock, n)) return true;
					// 자물쇠에 열쇠 빼기
					for(int i = 0; i < m; i ++){
						for(int j = 0 ; j < m ; j++){
							newLock[x+i][y+j] -= key[i][j];
						}
					}
				}
			}
		}
		
        return false;
    }
}

コード解釈

この問題の鍵は二つある.
1.90度に並べてもいいですか.
2.配列を増やして値を比較できますか?はい.
回転配列のための関数は覚えておいたほうがいいです.△正方形の配列で、長方形の配列は同じです.
まず大きさを3倍に増やして、あなたに割り当てます.正確にサイズを大きくすることができますが、計算が複雑になります.3倍でも大丈夫な理由は、nの大きさが必ずmより大きいからです.
90度に変換した関数を4回繰り返し、その値の中間が1であれば、正しい問題です.