如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
先分析分析，这个感觉我们可以对每一个方格进行搜索，从(1,1)-(3,4);
这12个格子进行一一的行走5个格子，每到5个格子方案数加一，我们只需要
把每一个格子的方案数全部记录下来就行了，需要记住最开始的格子
需要进行标记，以后就不能在搜索这个格子了，但是除了初始格子以外的
同样也是需要进行标记的，但是需要回溯进行标记的消除
根据题意我们有4个可以搜索的方向：上下左右
发现这样是错误的
比如
1 1 0 0
1 0 0 0
1 1 0 0
这样是没有办法搜索出来的
最后换了一种思路就是我们可以把这12个格子进行标号，就想图中给的那样
我们只需要从12个数中挑出5个数然后转换成坐标的形式，然后进行判断
这5个坐标是否连通就行了
从12个数中找出5个数有 792种
满足条件的有116种
#include <cstdio>
#include <cstring>
int chess[6][6];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int num[5],ans=0,sum=0,g;
void dfs_2(int sx,int sy)//判断5个数是否联通
{
int i;
for(i=0;i<4;++i)
{
int ex = sx + dx[i];
int ey = sy + dy[i];
if(chess[ex][ey]&&ex>0&&ex<4&&ey>0&&ey<5)
{
++g;//记录了一共经历了几个点
chess[ex][ey]=0;
dfs_2(ex,ey);
}
}
}
void dfs_1(int index,int k)//index代表下标
{
if(index==5)//当下标为5时表示已经从12个数中找到了5个数 C(12,5);
{
memset(chess,0,sizeof(chess));
++sum;
int j,sx,sy;
for(j=0;j<5;++j)//进行坐标的转换
{
sy=num[j]%4;
if(sy==0)
{
sx=num[j]/4;
sy=4;
}
else
sx=num[j]/4+1;
chess[sx][sy]=1;
}
g=1;
chess[sx][sy]=0;
dfs_2(sx,sy);//检查5个点是否连通
if(g==5)
++ans;
return ;
}
else
{
int i;
for(i=k+1;i<=12;++i)
{
num[index]=i;
dfs_1(index+1,i);
}
}
}
int main()
{
int i,j;
dfs_1(0,0);//从12个数中找出5个并存在num数组中
printf("%d\n",sum);//全部的组合数
printf("%d\n",ans); //最后的结果
return 0;
}