백준7538 Incomplete chess boards

작성일 | In

문제 링크

  • http://icpc.me/7578

사용 알고리즘

  • 이분 매칭

풀이

격자 그래프는 이분 그래프입니다.
Maximum Bipartite Matching이 Perfect Matching인지 확인하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

const int di[] = {1, -1, 0, 0};
const int dj[] = {0, 0, 1, -1};
inline int id(int i, int j){ return (i-1) * 8 + j; }

namespace BM{
    vector<int> G[66];
    int chk[66], par[66], pv;
    void Clear(){
        for(int i=0; i<66; i++) G[i].clear();
        memset(chk, 0, sizeof chk);
        memset(par, -1, sizeof par);
        pv = 0;
    }
    void AddEdge(int s, int e){ G[s].push_back(e); }
    bool DFS(int v){
        chk[v] = pv;
        for(auto i : G[v]){
            if(chk[i] == pv) continue;
            chk[i] = pv;
            if(par[i] == -1 || DFS(par[i])){
                par[i] = v; return true;
            }
        }
        return false;
    }
    int Run(){
        int ret = 0;
        for(int i=1; i<=8; i++) for(int j=1; j<=8; j++) if(i+j & 1) pv++, ret += DFS(id(i, j));
        return ret;
    }
}

const int N = 8;
bool Block[9][9];

void Solve(){
    BM::Clear();
    int a, b, c, d; cin >> a >> b >> c >> d;
    Block[a][b] = Block[c][d] = true;
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) {
        if(Block[i][j]) continue;
        for(int k=0; k<4; k++){
            int ii = i + di[k], jj = j + dj[k];
            if(ii < 1 || jj < 1 || ii > N || jj > N || Block[ii][jj]) continue;
            BM::AddEdge(id(i, j), id(ii, jj));
        }
    }
    int res = BM::Run() == 31;
    cout << res << "\n";
    Block[a][b] = Block[c][d] = false;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for(int tc=1; tc<=T; tc++){
        cout << "Scenario #" << tc << ":\n";
        Solve();
        cout << "\n";
    }
}