蓝桥杯 2015 决赛 2 四阶幻方

2019-11-11 03:51:26

字体：大中小

来源：转载

供稿：网友

把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时的所有方案数字，不要填写任何多余内容或说明文字

也是小学奥数题,不过这个稍微难点,难在时间上

裸DFS#include <bits/stdc++.h>using namespace std;list<int> li;int a[16] = {1};int ans = 0;int s = 0;bool ok(int i, int x){ if (i == 3) { s = a[0] + a[1] + a[2] + x; return true; } if (i == 7) return a[4] + a[5] + a[6] + x == s; if (i == 11) return a[8] + a[9] + a[10] + x == s; if (i == 12) return a[0] + a[4] + a[8] + x == s && a[3] + a[6] + a[9] + x == s; if (i == 13) return a[1] + a[5] + a[9] + x == s; if (i == 14) return a[2] + a[6] + a[10] + x == s; if (i == 15) return a[3] + a[7] + a[11] + x == s && a[12] + a[13] + a[14] + x == s && a[0] + a[5] + a[10] + x == s;}void dfs(int k){ if (k == 16) ans++; for (auto it = li.begin(); it != li.end(); it++) { if (ok(k, *it)) { a[k] = *it; it = li.erase(it); dfs(k + 1); it = li.insert(it, a[k]); } }}int main(){ for (int i = 2; i <= 16; i++) li.push_back(i); dfs(1); cout << ans << endl;}

用时80s, 需要等待很久这里写图片描述