剪邮票(暴力+DFS)

第七题：剪邮票

如【图】

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

请你计算，一共有多少种不同的剪取方法。

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

解析:

枚举每种情况,12个选5个,C(12,5)

判断5个是否连通

ac:

#include<bits/stdc++.h>
using namespace std;
int d[4]={1,-1,4,-4};
int vis[15];
int sign[15];

int dfs(int x)
{
    for(int i=0;i<4;i++)
    {
        if(x%4==0&&i==0)//不能+1
            continue;
        if(x%4==1&&i==1)//不能-1
            continue;
        int dx=x+d[i];
        if(dx>=1&&dx<=12&&vis[dx]==1&&sign[dx]==0)
        {
            sign[dx]=1;
            dfs(dx);
        }
    }
}

int main()
{
    int ans=0;
    memset(vis,0,sizeof(vis));
    memset(sign,0,sizeof(sign));

    for(int a=1;a<=12;a++)
        for(int b=a+1;b<=12;b++)
            for(int c=b+1;c<=12;c++)
                for(int d=c+1;d<=12;d++)
                    for(int e=d+1;e<=12;e++)//C(12,5)=792,枚举每种情况
                    {
                        vis[a]=vis[b]=vis[c]=vis[d]=vis[e]=1;
                        sign[a]=1;
                        dfs(a);
                        if(sign[b]==1&&sign[c]==1&&sign[d]==1&&sign[e]==1)
                            ans++;
                        vis[a]=vis[b]=vis[c]=vis[d]=vis[e]=0;
                        sign[a]=sign[b]=sign[c]=sign[d]=sign[e]=0;
                    }

    printf("%d \n",ans);
    return 0;
}