题目：Sudoku
匪夷所思的方法，匪夷所思的速度！！！
https://github.com/ttlast/ACM/blob/master/Dancing%20Link%20DLX/poj%203074.cpp
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int inf = 100000000; int flag; typedef long long LL; #define FF(i,A,s) for(int i = A[s];i != s;i = A[i]) const int maxm = 400400; const int maxn = 906; int used[maxn]; struct DLX{ int R[maxm],L[maxm],U[maxm],D[maxm]; int col[maxm],row[maxm]; int s[maxn];bool hash[maxn]; //重复覆盖 int pre,first,sz,NV,limit; void init(int n) //列的数目 { int i; for(i = 0;i <= n;i ++) { U[i] = i;D[i] = i; col[i] = i; // L[i] = i-1,R[i] = i+1; } NV = n;sz = n+1;pre = -1;first = 0; memset(s,0,sizeof(s)); } void insert(int i,int j) //一行一行的插入数据i行j列 { if(i != pre) //pre表示前一行，如果不同，就更新前面那行的左右 { R[sz-1] = first;L[first] = sz -1; pre = i;first = sz; } L[sz] = sz - 1;R[sz] = sz+1; //可以将j列看做矩阵的最底部. D[U[j]] = sz; D[sz] = j;U[sz] = U[j];U[j] = sz; row[sz] = i,col[sz] = j,s[j] ++; sz ++; } void finish() { R[sz-1] = first;L[first] = sz - 1;} void EXremove(int c){ //删除c列,而且与c有重复的行精确覆盖 L[R[c]] = L[c];R[L[c]] = R[c]; FF(i,D,c) FF(j,R,i) U[D[j]] = U[j],D[U[j]] = D[j],--s[col[j]]; } void EXresume(int c){ //恢复c列,而且与c有重复的行 FF(i,U,c) FF(j,L,i) ++s[col[j]],U[D[j]] = j,D[U[j]] = j; L[R[c]] = c;R[L[c]] = c; } //选择行，使每一列仅有一个 bool dfs(const int &k) //精确覆盖，选择了k行了。 { if(flag) return true; //if(k >= flag) return false; if(R[0] == 0) { //if(flag > k) flag = k; flag = 1; return true; } //if(R[0] == 0) return true; //找到解 int idx = R[0],i; for(i = R[0] ;i != 0;i = R[i]) if(s[idx] > s[i]) idx = i; EXremove(col[idx]); FF(i,D,idx){ used[row[i]] = 1; FF(j,R,i) EXremove(col[j]); if(dfs(k+1)) return true; //查找下一个。 FF(j,L,i) EXresume(col[j]); used[row[i]] = 0; } EXresume(col[idx]); return false; } //重复覆盖,选择最少行，所有的列被覆盖,后来添加的。 void remove(int & c) { FF(i,D,c) L[R[i]] = L[i],R[L[i]] = R[i]; } //去掉某列 void resume(int & c) { FF(i,U,c) L[R[i]] = i,R[L[i]] = i; } int h(){ //f启发函数 int ret = 0; memset(hash,false,sizeof(hash)); for(int c = R[0];c != 0;c = R[c]) if(!hash[c]){ //可以修改c != 0部分 hash[c] = true; ret ++; FF(i,D,c) FF(j,R,i) hash[col[j]] = true; } return ret; } //重复覆盖，只删除列不删除行 bool dfs(const int & k,int & limit) { if(k+h() >= limit) return false; if(R[0] == 0) { if(k < limit) limit = k; return true; } int idx = R[0],i; for(i = R[0] ;i != 0;i = R[i]) if(s[idx] > s[i]) idx = i; FF(i,D,idx){ remove(i); FF(j,R,i) remove(j); if(dfs(k+1,limit)) return true; FF(j,L,i) resume(j); resume(i); } return false; } int astar() //or 二分。 { limit = h(); while(!dfs(0,limit)) limit ++; //修改点，limit最后期限 return limit; } }; DLX dlx; char c[100]; int map[730]; int main() { int i,j,k,pos,row,cnt; while(gets(c)) { if(c[0] == 'e') break; dlx.init(324); row = 1; memset(used,0,sizeof(used)); for(i = 0;i < 9;i ++) for(j = 0;j < 9;j ++) { if(c[i*9+j] == '.'){ for(k = 1;k <= 9;k ++) { dlx.insert(row,i*9+k); //行+数字 dlx.insert(row,81+j*9+k); //列+数 dlx.insert(row,162+(i/3+(j/3)*3)*9+k); //小方块号号 dlx.insert(row,243+i*9+j+1); //座位 map[row++] = k; } }else{ cnt = c[i*9+j] - '0'; dlx.insert(row,i*9+cnt); //行+数字 dlx.insert(row,81+j*9+cnt); //列+数 dlx.insert(row,162+(i/3+(j/3)*3)*9+cnt); //小方块号 dlx.insert(row,243+i*9+j+1); //座位 map[row++] = cnt; } } dlx.finish(); flag = 0; if(dlx.dfs(0)) { for(i = 0;i < row;i ++) if(used[i]) printf("%d",map[i]); printf(" "); }else puts("NO"); } return 0; }