1265: [蓝桥杯2015决赛]四阶幻方

题目链接:1265: [蓝桥杯2015决赛]四阶幻方

题目描述
把1~16的数字填入4x4的方格中，使得行、列以及两个对角线的和都相等，满足这样的特征时称为：四阶幻方。
四阶幻方可能有很多方案。如果固定左上角为1，请计算一共有多少种方案。
比如：
1 2 15 16
12 14 3 5
13 7 10 4
8 11 6 9
以及：
1 12 13 8
2 14 7 11
15 3 10 6
16 5 4 9
就可以算为两种不同的方案。
输出
请提交左上角固定为1时的所有方案数字

题意：就是左上角固定填好1，其他位置填数，每个数只能填一次，然后每行，每列，两条对角线的和都相等就算符合条件，求出一共有多少种符合条件的方案

思路：DFS再剪枝下，这题是填空题，最后直接输出即可

代码：

#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[5][5];
int book[17];
int sum=34;
int ans=0;

bool jd(int i)  // 检查行
{ int num=0; for(int j=0;j<4;j++) num+=a[i][j]; if(num!=sum) return false; return true;
}

bool check() // 核对是否满足要求
{ int num1=a[0][0]+a[1][1]+a[2][2]+a[3][3];// 主对角线 if(num1!=sum) return false; int num2=a[0][3]+a[1][2]+a[2][1]+a[3][0]; //副对角线 if(num2!=sum) return false; for(int i=0;i<4;i++) //行 { if(!jd(i)) return false; } for(int j=0;j<4;j++) // 列 { int k=a[0][j]+a[1][j]+a[2][j]+a[3][j]; if(k!=sum) return false; } return true;
}

void dfs(int n)
{ if(n==16) { if(check()) ans++; return ; } if(n%4==0) // 剪枝下 { if(!jd(n/4-1)) return ; } for(int i=2;i<17;i++)  //填充 { if(!book[i]) { book[i]=1; a[n/4][n%4]=i; dfs(n+1); book[i]=0; } }
}

int main()
{ a[0][0]=1; dfs(1); cout<<ans<<endl; //cout<<416<<endl; //最后直接输出即可 return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
 

加油！

共同努力！

Keafmd

本人博客园同文链接：牛哄哄的柯南

文章来源: keafmd.blog.csdn.net，作者：牛哄哄的柯南，版权归原作者所有，如需转载，请联系作者。

原文链接：keafmd.blog.csdn.net/article/details/107733992