[プログラマー]2020 KAKAO BLIND RECRUITMENT:鍵と鍵(C++)

18121 ワード
programmers algorithm cpp テキストリンク
質問リンク:鍵と鍵

[質問へのアクセス]


制限事項が小さいので,ロックと接触する部分が最小になるまですべて探索できる.

｣探索範囲


はこのようにarrサイズ全体を最大範囲に拡大してナビゲーションすればよいが、どうせナビゲーション時に起点を見つけてナビゲーションすればよい(キーのsize)+(ロックのsize)−1であればよい.

｣探索方法


まずarr配列を初期化し,初期化時にarr配列の中間にlockの値を割り当てる.
次にkeyの値を開始点に従ってarr配列に入れます.
例えばは、上図のように、始点が(1,1)であれば、オーバーラップ状態となる.

べんべつきかいてん


ナビゲーションキーを移動する前に、回転する場合もすべて試します.4回回転すると元の状態に戻るので、総回転を4回して試してみることができます.
回転するときに、キーのサイズが4であると仮定するルールがあります.
(0,0)の位置(3,0)に、位置の値があります.
(0,1)ビット上(2,0)ビット上の値が来ました.
すなわち,(i,j)位置で(keyのsize−1−j,i)位置の値を発見できるルールである.
ソースコードのコメントを真剣にフォローすれば、分かりやすいです.

[ソースコード]

#include <string>
#include <vector>
#include <cstring>

using namespace std;
int arr[60][60];
int ksize = 0;
int lsize = 0;

void makeinit(vector<vector<int>> lock) {
    memset(arr, 0, sizeof(arr));
    int start = ksize-1;
    int end = start+lsize;
    
    for(int i=start ; i<end ; i++) {
        for(int j=start ; j<end ; j++) {
            arr[i][j] = lock[i-start][j-start];
        }
    }
}

void printKey(vector<vector<int>> key, int y, int x) {
    int size = key.size();
    for(int i=y ; i<y+size ; i++) {
        for(int j=x ; j<x+size ; j++) {
            arr[i][j] += key[i-y][j-x];
        }
    }
}

bool checkLock() {
    int start = ksize-1;
    int end = start+lsize;
    
    for(int i=start ; i<end ; i++) {
        for(int j=start ; j<end ; j++) {
            if(arr[i][j]!=1) return false;
        }
    }
    
    return true;
}

bool checkKey(vector<vector<int>> key, int y, int x) {
    printKey(key, y, x); // 현재 key를 arr배열에 대입
    return checkLock(); // 자물쇠가 전부 1로 되어있는지 검사
}

vector<vector<int>> spinKey(vector<vector<int>> key) {
    vector<vector<int>> result;
    
    for(int i=0 ; i<ksize ; i++) {
        vector<int> temp;
        for(int j=0 ; j<ksize ; j++) {
            temp.push_back(key[ksize-j-1][i]);
        }
        result.push_back(temp);
    }
    
    return result;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    ksize = key.size();
    lsize = lock.size();
    int end = key.size()+lock.size()-1; // 탐색해야하는 지점의 끝

    for(int i=0 ; i<end ; i++) { 
        for(int j=0 ; j<end; j++) { // key 스타트 지점
            for(int k=0 ; k<4 ; k++) { // 4번 회전하면 원래 key로 돌아옴
                makeinit(lock); // 전체 배열 초기화
                if(checkKey(key, i, j)) { // key를 대입해서 lock이 풀리는지 검사
                    return true;
                } else {
                    key = spinKey(key); // key를 시계방향으로 회전
                }
            }
        }
    }
    
    return false;
}
iOSベース:毎回覚えられないコード(更新継続)
GitLabバックアップとリストアにおける権限の問題