Codeforces #1494B Berland Crossword

문제

https://codeforces.com/problemset/problem/1494/B

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

bool solve(){
    int n, U, R, D, L;
    cin >> n >> U >> R >> D >> L;
    for(int mask = 0; mask < 16; mask++){
        int rU = U, rR = R, rD = D, rL = L;
        if(mask & 1){
            rU -= 1;
            rL -= 1;
        }
        if(mask & 2){
            rU -= 1;
            rR -= 1;
        }
        if(mask & 4){
            rD -= 1;
            rL -= 1;
        }
        if(mask & 8){
            rD -= 1;
            rR -= 1;
        }
        vector<int> a = {rU, rR, rD, rL};
        if(*min_element(all(a)) >= 0 && *max_element(all(a)) <= n-2) return true;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        if(solve()) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

n x n 으로 이루어진 격자가 있다. 상하좌우 가장자리 행과 열에 색칠되어야 할 칸의 개수가 주어질 때, 조건에 맞게 색칠할 수 있는지를 묻는 문제이다.

다른 방향의 가장자리와 공유하는 칸은 네개의 모서리 부분으로, 색칠 여부에 따라 2⁴ 개의 경우의 수가 존재한다. 어떻게 모든 경우의 수를 세어야 할 지 감이 잘 오지 않았는데 bitmask 기법을 이용하면 쉽게 확인할 수 있었다.

0부터 15까지 정수를 비트로 생각하여 색칠된 칸(1) 일 경우에만 색칠해야 하는 칸의 개수를 줄여 나간다. 각 경우마다 색칠해야 할 칸의 개수가 모두 0 이상 n-2 이하일 때 solution 이 존재한다고 본다. 음수가 존재하는 경우는 모서리 부분의 영향으로 더 많이 색칠 된 경우, n-2 보다 큰 경우는 모서리가 색칠되어야만 하지만 색칠되지 않은 경우를 뜻한다.