蓝桥杯-剪邮票【全排列+联通块dfs】

剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。

图7-2.jpg

图7-3.jpg

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

#include<bits/stdc++.h>
using namespace std;

int ans;

void dfs(int g[3][4],int x,int y)
{
    g[x][y]=0;
    if(x+1<=2&&g[x+1][y]==1)
        dfs(g,x+1,y);
    if(x-1>=0&&g[x-1][y]==1)
        dfs(g,x-1,y);
    if(y+1<=3&&g[x][y+1]==1)
        dfs(g,x,y+1);
    if(y-1>=0&&g[x][y-1]==1)
        dfs(g,x,y-1);
}

bool check(int a[12])
{
    int cnt=0;
    int g[3][4];
    memset(g,0,sizeof(g));
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<4; j++)
        {
            g[i][j]=a[cnt++];
        }
    }
    int sum=0;
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<4; j++)
        {
            if(g[i][j])
            {
                dfs(g,i,j);
                sum++;
            }
        }
    }
    if(sum==1) return true;
    return false;
}

int main()
{
    int a[12]= {0,0,0,0,0,0,0,1,1,1,1,1};
    do
    {
        if(check(a))
            ans++;
    }
    while(next_permutation(a,a+12));
    cout<<ans<<endl;

}