#include <string>
#include <vector>
#include <iostream>
using namespace std;
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
int tot_cnt = 0;
for(int r=0;r<lock.size();r++)
for(int c=0;c<lock.front().size();c++)
if(lock[r][c] == 0) tot_cnt++;
for(int n=0;n<4;n++)
{
vector<vector<int>> tmp(key.begin(), key.end());
int cur_c = key.front().size();
for(int a=0;a<key.size();a++)
{
cur_c--;
for(int b=0;b<key[a].size();b++)
tmp[b][cur_c] = key[a][b];
}
key = tmp;
int st_r = -lock.size()+1;
int st_c = -lock.front().size()+1;
for(int dr=st_r;dr<(int)lock.size();dr++)
{
for(int dc=st_c;dc<(int)lock.front().size();dc++)
{
bool flag = true;
int cnt = 0;
for(int r=0;r<key.size();r++)
{
for(int c=0;c<key.front().size();c++)
{
int nr = r + dr;
int nc = c + dc;
if(nr<0 or nc<0 or nr>=lock.size() or nc>=lock.front().size()) continue;
if(key[r][c] == lock[nr][nc]) goto stop;
if(key[r][c] == 1) cnt++;
}
}
stop:;
if(cnt == tot_cnt) {
return true;
}
}
}
}
return false;
}
- 핵심
자물쇠의 총 구멍 개수(tot_cnt)
를 구해서 열쇠로 매운 개수(cnt)
와 비교
해서 같은 경우에만 true!
--> 현재 key
로 일부분은 채워
질 수 있지만, 반드시 정답
은 모든 자물쇠 구멍을 채워야 하기 때문
이동하는 좌표
를 구할 때 행,열 간 차이
를 나타내는 dr / dc
의 초기 값
을 (-N+1)
으로 설정
--> key
를 오른쪽 / 아래 방향
뿐만 아니라 위/ 왼쪽 방향
으로도 옮길 수 있기 때문!