本文最后更新于 1163 天前,其中的信息可能已经有所发展或是发生改变。
#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;
}
Post Views: 175