백준 17106번 빙고

http://icpc.me/17106

17106번: 빙고

 

풀이

25개의 빙고 칸 각각을 색칠하거나 색칠하지 않을 수 있으므로 빙고 칸을 채우는 경우의 수는 $2^{25}$가지입니다. 모든 경우를 살펴보며 각 경우의 수마다 모든 칸이 올바르게 색칠되었는지를 체크하는 코드를 작성하면 정답을 찾을 수 있습니다. 

 

다소 문제가 되는 칸은 B5입니다. 다른 칸들은 모두 빙고판의 상태를 통해 올바르게 색칠되었는지 알 수 있지만 이 칸은 그렇지 않습니다. B5가 참이라고 가정하고 완전탐색을 돌리면 가능한 정답 목록을 얻을 수 있고, 이때 얻은 정답이 여러 개라면 B5는 참, 하나뿐이거나 없다면 B5는 거짓이 됩니다. 이렇게 B5의 값을 얻은 뒤 나머지 칸들을 채우는 모든 경우를 탐색해주면 됩니다. 

 

C2도 빙고판의 상태만으로는 조건을 만족하는지 알 수 없지만 이 칸은 색칠하든 말든 상관없다는 것을 쉽게 알 수 있습니다.

 

코드

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0), cin.tie(nullptr)
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define fi first
#define se second
#define cat(a, b) a##b
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll S = 100 + 10, MOD = 998244353;
 
struct st {
    int i;
    bool operator()(int r, int c) {
        return (i & (1 << (r * 5 + c)));
    }
    void print() {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++)
                cout << (tmp(i, j) ? '#' : '.'); //((i & (1 << (i * 5 + j))) ? "#" : ".");
            cout << '\n';
        }
        cout << '\n';
    }
    bool row(int r) {
        for (int i = 0; i < 5; i++) 
            if (!tmp(r, i)) return false;
        return true;
    }
    bool col(int c) {
        for (int i = 0; i < 5; i++)
            if (!tmp(i, c)) return false;
        return true;
    }
    bool dia1() { 
        // ↘
        for (int i = 0; i < 5; i++)
            if (!tmp(i, i)) return false;
        return true;
    }
    bool dia2() {
        // ↙
        for (int i = 0; i < 5; i++)
            if (!tmp(i, 4 - i)) return false;
        return true;
    }
    bool is_bingo(int r, int c) {
        if (r == c and dia1()) return true;
        if (r == 4 - c and dia2()) return true;
        return row(r) or col(c);
    }
    int count(function<bool(int, int)> f) {
        int ret = 0;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++)
                ret += f(i, j);
        }
        return ret;
    }
    bool tmp(int r, int c) {
        return (i & (1 << (r * 5 + c)));
    }
} now;
function<bool()> f[5][5];
 
int main() {
    fast;
 
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
 
    f[0][0] = []() { 
        return !now.dia2();
    };
    f[0][1] = []() {
        return !(now.row(0) or now.col(1));
    };
    f[0][2] = []() {
        return now.dia1();
    };
    f[0][3] = []() {
        return now(3, 3);
    };
    f[0][4] = []() {
        return now.is_bingo(0, 4);
    };
    f[1][0] = []() {
        return !now(3, 0);
    };
    f[1][1] = []() {
        if (!now.dia1() and !now.dia2()) return false;
        bool chk1 = false, chk2 = false;
        for (int i = 0; i < 5; i++) {
            chk1 = chk1 or now.row(i);
            chk2 = chk2 or now.col(i);
        }
        return chk1 and chk2;
    };
    f[1][2] = []() {
        return now(1, 2);
    };
    f[1][3] = []() {
        return now.count([&](int r, int c) {return now(r, c); }) <= 17;
    };
    f[1][4] = []() {
        return now.count([&](int r, int c) {return now.is_bingo(r, c); }) % 2 == 0;
    };
    f[2][0] = []() {
        return now.is_bingo(2, 0);
    };
    f[2][1] = []() {
        return now.count([&](int r, int c) {return now(r, c) and !now.is_bingo(r, c); }) >= 5;
    };
    f[2][2] = []() {
        return !now(2, 2) or now.is_bingo(2, 2);
    };
    f[2][3] = []() {
        int cnt = 0;
        for (int i = 0; i < 5; i++)
            cnt += now.col(i);
        return cnt >= 2;
    };
    f[2][4] = []() {
        return now.count([&](int r, int c) {return !now.is_bingo(r, c); }) >= 10;
    };
    f[3][0] = []() {
        return !now(1, 0);
    };
    f[3][1] = []() {
        return now.row(1) or now.col(3);
    };
    f[3][2] = []() {
        int cnt = 0;
        for (int i = 0; i < 5; i++)
            cnt += now(i, 2);
        return cnt <= 3;
    };
    f[3][3] = []() {
        return now(0, 3);
    };
    f[3][4] = []() {
        return now.dia1() or now.dia2();
    };
    f[4][0] = []() {
        return now(4, 4);
    };
    f[4][1] = []() {
        return ??;
    };
    f[4][2] = []() {
        return now(4, 2);
    };
    f[4][3] = []() {
        int cnt = (int)now.dia1() + (int)now.dia2();
        for (int i = 0; i < 5; i++)
            cnt += (int)now.row(i) + (int)now.col(i);
        return cnt >= 3;
    };
    f[4][4] = []() {
        return now(4, 0);
    };
 
    for (now.i = 0; now.i < (1 << 25); now.i++) {
        bool valid = true;
        if (now.i % 200000 == 0) cout << now.i << '\n';
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (now(i, j) != f[i][j]()) {
                    valid = false;
                    break;
                }
            }
        }
        if (valid) {
            cout << now.i << '\n';
            now.print();
        }
    }
}

 

비트마스킹을 통해 모든 $2^{25}$가지 경우의 수를 쉽게 살펴볼 수 있습니다. 각 칸마다 올바르게 색칠되었는지 여부를 알아내는 함수를 만들었고, 함수를 쉽게 만들기 위해 객체를 만들어 int형 변수 하나를 $5\times 5$ 배열처럼 접근할 수 있게 해주는 메서드, 특정 행/열/대각선이 모두 색칠되었는지 체크하는 메서드, 특정 칸이 빙고의 일부인지 체크하는 메서드, 조건에 맞는 칸의 수를 세는 메서드 등 자주 사용되는 기능을 추가했습니다. 

 

사족

가능한 정답이 여러 개인지, 답이 무엇인지는 직접 알아보시기 바랍니다.

칸의 조건을 잘 이용하면 경우의 수를 많이 줄일 수 있겠지만 귀찮고 굳이 줄이지 않아도 로컬에서는 충분히 구할 수 있기 때문에 생략했습니다.

똑똑한 분들은 코드 없이 그냥 푸시는 것 같은데.. 

저는 손으로 풀어 보려다 포기했습니다ㅠㅠ