2016蓝桥杯省赛C/C++A组第七题 剪邮票（暴力+并查集）

题意：有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）

分析：暴力+并查集。

1、记录下每个数字所在位置。

2、先枚举各不相同的5个数的所有可能情况（不包括数字种类相同但次序不同的情况）。

2、然后判断若其中某两个数字相邻则加入一个连通块，如果最终只有一个连通块，说明5个数字是通过相邻关系连在一起的，符合要求。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define lowbit(x) (x & (-x))

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 5000 + 10;

const int MAXT = 10000 + 10;

using namespace std;

int stax[20];

int stay[20];

int fa[20];

int a[10];

int ans;

int Find(int x){

    return fa[x] = (fa[x] == x) ? x : Find(fa[x]);

}

bool judge(){

    for(int i = 0; i < 20; ++i) fa[i] = i;

    for(int i = 0; i < 5; ++i){

        int tmpx = stax[a[i]];

        int tmpy = stay[a[i]];

        for(int j = 0; j < 5; ++j){

            if(i == j) continue;

            int tx = stax[a[j]];

            int ty = stay[a[j]];

            int x = abs(tmpx - tx);

            int y = abs(tmpy - ty);

            if((x == 0 && y == 1) || (x == 1 && y == 0)){

                int ii = Find(i);

                int jj = Find(j);

                if(ii == jj) continue;

                if(ii < jj) fa[jj] = ii;

                else fa[ii] = jj;

            }

        }

    }

    set<int> s;

    for(int i = 0; i < 5; ++i){

        s.insert(Find(i));

    }

    return s.size() == 1;

}

void dfs(int cur, int st){

    if(cur == 5){

        if(judge()){

            ++ans;

        }

        return;

    }

    for(int i = st + 1; i <= 12; ++i){

        a[cur] = i;

        dfs(cur + 1, i);

    }

}

int main(){

    int cnt = 0;

    for(int i = 1; i <= 3; ++i){

        for(int j = 1; j <= 4; ++j){

            ++cnt;

            stax[cnt] = i;

            stay[cnt] = j;

        }

    }

    ans = 0;

    dfs(0, 0);

    printf("%d\n", ans);

    return 0;

}