时间限制: 1 Sec 内存限制: 256 MB
题目描述
如图的五星图案节点填上数字:1~12,除去7和11。
要求每条直线上数字和相等。
如图就是恰当的填法。
请你利用计算机搜索所有可能的填法有多少种。
注意:旋转或镜像后相同的算同一种填法。
输出
请提交表示方案数目的整数,不要填写任何其它内容。
题意:就是在这个五角星中按要求填数,但是要出去对称和旋转的情况
思路:就类似方格填数,但是这是个五角星,所以就相当于十个位置,然后按照规定的方式让所有和相等。特别注意下就是题中要求(旋转或镜像后相同的算同一种填法),五角星旋转共有五种可能,再算上对称,所以要拿最后的结果除以(5*2)。
1265: [蓝桥杯2015决赛]四阶幻方:类似这个题,想法是一样的,只是形状不一样,填数方式以及验证求和的方式不同了。
看这个图会更清楚代码中的那个数组是如何相加的
代码:
#pragma GCC optimize(2) #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<map> #include<stack> #include<set> #include<vector> #include<queue> #include<iomanip> using namespace std; int a[]={1,2,3,4,5,6,8,9,10,12}; int num=0; bool check(int a[]) // 按照五角星的形状求和 { int num1=a[0]+a[2]+a[5]+a[8]; int num2=a[1]+a[2]+a[3]+a[4]; int num3=a[0]+a[3]+a[6]+a[9]; int num4=a[1]+a[5]+a[7]+a[9]; int num5=a[4]+a[6]+a[7]+a[8]; if(num1==num2&&num2==num3&&num3==num4&&num4==num5) return true; return false; } void dfs(int n) { if(n==9) { if(check(a)) num++; return ; } for(int i=n;i<10;i++) //填数 { int t=a[i]; a[i]=a[n]; a[n]=t; dfs(n+1); t=a[i]; a[i]=a[n]; a[n]=t; } } int main() { dfs(0); printf("%d\n",num/10);//这里注意下,除去旋转和对称的情况 return 0; }