lv3 자물쇠와 열쇠

개빡세다.

 

특히 

같이 key의 순차적인 탐색을 어떻게 하면 좀더 예쁘게 할 수 있을까....

 

답은 LOCK을 KEY의 탐색까지 덮히는 범위의 board를 만들어 준다.

 

이렇게 말이다.

 

그리고 board[][]의 가운데에 lock[][]을 넣어줘야 한다.

즉, board[m-1][m-1] ~ board[m+n-2] 에다가 lock[0][0] ~ lock[n-1][n-1]을 넣어준다.

여기서 조금 더 쉽게 넣는방법으로 for문 안에 변수를 2개씩 넣어주는 테크닉이 있다.

 

이것은 56~62번째 줄에 된다.

 

key의 rotate는 정사각형이니깐 쉬워서 넘어간다.

 

그다음 key 를 0 ~ m+n-2 부터 탐색하면서 xor을 하고  board에서 lock 부분이 전부 1이면 자물쇠가 맞는것이다.

이 과정은 gogo 함수 이다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
 
int m; // key
int n; // lock
int board_size; // 2 * m + n - 2;
vector<vector<int>> rotate(vector<vector<int>> key)
{
    vector<vector<int>> key2;
 
    for (int i = 0; i < key[0].size(); i++)
    {
        vector<int> tmp;
        for (int j = key.size() - 1; j >= 0; j--)
            tmp.push_back(key[j][i]);
        key2.push_back(tmp);
    }
 
    return key2;
}
 
bool gogo(int sx, int sy, vector<vector<int>> board, vector<vector<int>> key)
{
    for (int i = 0; i < key.size(); i++)
    {
        for (int j = 0; j < key.size(); j++)
        {
            board[i + sx][j + sy] = (board[i + sx][j + sy] ^ key[i][j]);
        }
    }
    int cnt = 0;
    for (int i = m - 1; i < m + n - 1; i++)
    {
        for (int j = m - 1; j < m + n - 1; j++)
        {
            cnt += board[i][j];
        }
    }
    if (cnt == n * n)
        return true;
    else
        return false;
}
 
bool solution(vector<vector<int>> key, vector<vector<int>> lock)
{
 
    m = key.size();
    n = lock.size();
    board_size = 2 * m + n - 2;
    vector<vector<int>> board(board_size, vector<int>(board_size, 0));
    // lock 의 가운데는 m-1 ~ m+n-2 이다.
    for (int i = 0, ii = m - 1; ii < m + n - 1; i++, ii++)
    {
        for (int j = 0, jj = m - 1; jj < m + n - 1; j++, jj++)
        {
            board[ii][jj] = lock[i][j];
        }
    }
 
    /*
    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board[0].size(); j++)
            cout << board[i][j] << ' ';
        cout << '\n';
    }
    */
 
    vector<vector<int>> key2 = rotate(key);
    vector<vector<int>> key3 = rotate(key2);
    vector<vector<int>> key4 = rotate(key3);
 
    // lock 의 가운데는 m-1 ~ m+n-2 이다.
    // total 거리는 2 * m + n - 2;
 
 
    for (int i = 0; i <= m + n - 2; i++)
    {
        for (int j = 0; j <= m + n - 2; j++)
        {
            if (gogo(i, j, board, key))
                return true;
            if (gogo(i, j, board, key2))
                return true;
            if (gogo(i, j, board, key3))
                return true;
            if (gogo(i, j, board, key4))
                return true;
        }
    }
    return false;
 
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    vector<vector<int>> key = { {0,0,0}, {1,0,0}, {0,1,1} };
    vector<vector<int>> lock = { {1,1,1}, {1,1,0}, {1,0,1} };
 
    cout <<solution(key, lock);
 
}