[アルゴリズム解答]プログラマーロックとキー

プログラマーのSweekleChallengeは3週間の質問を見て、何で問題を解いたのか知りたいです.単純に実施するだけではあまり効率が悪いのではないでしょうか~ということでオープンチャットルームでキーワードやヒントを聞いてみたところ、どちらも正しい実施という結果になりました!またこの問題については似ていますがもっと簡単な質問でKakao出題をおすすめしました!だからこの問題を解決してから3週目のWeeklyChallenge問題です!
そこで、今日解決した問題は、プログラマーの中で解決できる2020年のKACAブラインド採用機が鍵と鍵を出すことです.

問題の説明

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

解答方法

理解を助けるために、上記の例の画像を視覚的に見ると以下のようになります.

大きな枠組みの解法は以下の通りである.

キーは回転可能であり、各方向4番について、以下の手順で開くことができるかどうかを探索しなければならない.

図

に示すように探索を行う.

黒いボックスはロックされた領域です.

黄色のボックスは重要な領域です.

キーがロックに入る可能性のあるすべての場合の数を探索するために、キーを左上隅の黄色部分から右下隅の黄色領域に移動する.

位のレッスンを終えるために、オレンジ色のエリアの大きなプレートを作って使いました.回路基板のロック位置はlock要素であり、残りは-1初期化

である.

の上の説明に示すように、キーを移動すると、キーがlockに重なる部分(-1ではない)には、重複するlock値とキー値が加算されます.

でlockのブラウズを続行でき、すべての値が1の場合、ロックを解除できます.(0だと埋まっていない部分2だと両方とも回転する部分!)

上記の手順と比較するためにコードが見られ、大きな流れごとに注釈が付けられているので、一緒に見ると分かりやすいはず!想像以上に難しい問題ではない.複数の2次元配列を扱う必要があるので,ゲートの重複に対してインデックス管理をしっかりと行えば,逐次漸進的に実施するだけでよい.

コード#コード#

import java.util.Arrays;
class Solution {
    public static int[][] rotation(int[][] matrix){
        int size = matrix.length;
        int[][] result = new int[size][size];
        for(int i=0; i<size; i++){
            for(int j=0; j<size; j++){
                result[j][size-1-i] = matrix[i][j];
            }
        }
        return result;
    }

    public static boolean isPossible(int[][] key, int[][] lock){
        int m = key.length;
        int n = lock.length;
        int board_size = n + (2*(m-1));
        int[][] board = new int[board_size][board_size];
        int[] arr;

        // key 이동
        int temp;
        boolean index;
        for(int i=0; i<(m-1)+n; i++){
            for(int j=0; j<(m-1)+n; j++){
                index = true;
                // init board
                for(int k=0; k<board_size; k++){
                    arr = new int[board_size];
                    Arrays.fill(arr, -1);
                    board[k] = arr;
                }
                for(int k=0; k<lock.length; k++){
                    for(int l=0; l<lock.length; l++){
                        board[k+m-1][l+m-1] = lock[k][l];
                    }
                }
                // key 이동
                for(int k=0; k<key.length; k++){
                    for(int l=0; l<key.length; l++){
                         // 겹치는 부분 반영
                        if(board[i+k][j+l]!=-1){
                            board[i+k][j+l] += key[k][l];
                        }
                    }
                }
                // lock 검사
                for(int k=0; k<lock.length; k++){
                    for(int l=0; l<lock.length; l++){
                        temp = board[k+m-1][l+m-1];
                        if(temp != 1){
                            index = false;
                            break;
                        }
                    }
                    if(!index) break;
                }
                // 검사 결과 확인
                if(index) return true;
            }
        }
        return false;
    }

    public boolean solution(int[][] key, int[][] lock) {
        for(int i=0; i<4; i++){
            if(i!=0) key = rotation(key);
            if(isPossible(key, lock)) return true;
        }
        return false;
    }
}