六角填数(深度优先搜索)
如图所示六角形中,填入1~12的数字。使得每条直线上的数字之和都相同。
图中,已经替你填好了3个数字,请你计算星号位置所代表的数字是多少?
方法一:dfs
#include<iostream>
#include<cstring>#include<cstdio>
#include<algorithm>
using namespace std;
int a[13],book[13]; //a数组用来储存 圆圈内的数字
// book数组用来标记1-12个数,防止出现重复
void dfs(int x) //x代表a数组的下标 ,从零开始
{
int i;
if(x==1||x==2||x==12)
{
dfs(x+1);
return;
}
if(x==13) //填好12个数后,判断是否满足条件
{
int b[6];
b[0]=a[1]+a[3]+a[6]+a[8];
b[1]=a[1]+a[4]+a[7]+a[11];
b[2]=a[2]+a[3]+a[4]+a[5];
b[3]=a[2]+a[6]+a[9]+a[12];
b[4]=a[5]+a[7]+a[10]+a[12];
b[5]=a[8]+a[9]+a[10]+a[11];
for(i=0;i<5;i++)
{
if(b[i]!=b[i+1])
{
return;
}
}
cout<<a[6];
}
for(i=1;i<13;i++)
{
if(book[i]==0) //判断i是否未使用过
{
book[i]=1; //标记
a[x]=i;
dfs(x+1);
book[i]=0; //取消标记
}
}
}
int main()
{
a[1]=1;a[2]=8;a[12]=3;
book[1]=1;book[8]=1;book[3]=1;
dfs(1);
return 0;
}
方法二:全排列函数
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
int a[13]={0,1,3,8,2,4,5,6,7,9,10,11,12};
sort(a+1,a+13);
do
{
int b[6],f=1;
b[0]=a[1]+a[3]+a[6]+a[8];
b[1]=a[1]+a[4]+a[7]+a[11];
b[2]=a[2]+a[3]+a[4]+a[5];
b[3]=a[2]+a[6]+a[9]+a[12];
b[4]=a[5]+a[7]+a[10]+a[12];
b[5]=a[8]+a[9]+a[10]+a[11];
for(int i=0;i<5;i++)
{
if(b[i]!=b[i+1])
{
f=0;
break;
}
}
if(f==0)
continue;
else
{
cout<<a[6];
break;
}
}while(next_permutation(a+1,a+13));
return 0;
}