方格填數 如下的10個格子 
填入0~9的數字。要求：連續的兩個數字不能相鄰。 （左右、上下、對角都算相鄰） 一共有多少種可能的填數方案？
DFS就好 但是, 我加了一個list的優化 更要命的是 這個list是用STL實現的 (好吧,其實是我已經懶到手寫鏈表都不會了) 下面普及list的用法 list.erase(it) 這個是函數 返回刪除元素的下一個迭代器 e.g list = [0, 1, 2, 3, 4 …] it = list.erase(list.begin()) *it = 1 同樣 list.insert(it, x)也是個函數,返回的是插入這個元素的迭代器 e.g list = [0, 1, 2, 3, 4 …] it = list.insert(list.begin(), -1) *it = -1 特別注意 是在前面插入的 所以此時 list 變成 [-1, 0, 1, 2, …] 總之這樣,就可以解決藍橋杯里面一切小學奧數問題 并且用了STL, 非常優雅
#include <bits/stdc++.h>using namespace std;list<int> li;int g[20];bool adj(int a, int b){ return abs(a - b) > 1;}bool ok(int i, int x){ if (i == 0) return true; if (i == 1) return adj(x, g[0]); if (i == 2) return adj(x, g[1]); if (i == 3) return adj(x, g[0]); if (i == 4) return adj(x, g[0]) && adj(x, g[1]) && adj(x, g[3]); if (i == 5) return adj(x, g[0]) && adj(x, g[1]) && adj(x, g[2]) && adj(x, g[4]); if (i == 6) return adj(x, g[1]) && adj(x, g[2]) && adj(x, g[5]); if (i == 7) return adj(x, g[3]) && adj(x, g[4]); if (i == 8) return adj(x, g[3]) && adj(x, g[4]) && adj(x, g[5]) && adj(x, g[7]); if (i == 9) return adj(x, g[4]) && adj(x, g[5]) && adj(x, g[6]) && adj(x, g[8]);}int ans = 0;void dfs(int k){ if (k == 10) ans++; for (auto it = li.begin(); it != li.end(); it++) { if (ok(k, *it)) { g[k] = *it; it = li.erase(it); dfs(k + 1); it = li.insert(it, g[k]); } }}int main(){ for (int i = 0; i < 10; i++) { li.push_back(i); } dfs(0); cout << ans << endl;}新聞熱點
疑難解答
