方格填数 如下的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;}新闻热点
疑难解答
