藍橋杯 2015 決賽 2 四階幻方

2019-11-11 02:31:03

字體：大中小

來源：轉載

供稿：網友

把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, 需要等待很久這里寫圖片描述