Dancing Links 是一种数据结构,用于精确覆盖。详情去下面链接学;感谢大牛总结。
学习资料: http://www.cnblogs.com/grenet/p/3145800.html http://blog.csdn.net/mu399/article/details/7627862
题意:就是给你一个随机的九宫格,问你答案是多少?
算法:Dancing Links
思路:Dancing Links的行和列都是从1开始的;这里除了本身给出的格子有数字外,其他格子都要从1~9选填,所以行最大就是N*N*N;列:每一行都有4个列,此格子有数字、此格子所在行有数字K、此格子所在列有数字K、此格子九宫格有数字K
代码:其实抄的摸版,摸版刚好做这题。
1 #include <iostream> 2 #include <vector> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <cstdio> 7 #include <map> 8 #include <math.h> 9 10 using namespace std; 11 12 const int INF = 0x3f3f3f3f; 13 const int N = 9; 14 const int MaxN = N*N*N + 10; 15 const int MaxM = N*N*4 + 10; 16 const int maxnode = MaxN*4 + MaxM + 10; 17 char g[MaxN]; 18 struct DLX{ 19 int n,m,size; 20 int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode]; 21 int H[MaxN],S[MaxM]; 22 int ansd,ans[MaxN]; 23 void init(int _n,int _m){ 24 n = _n , m = _m; 25 for(int i = 0;i <= m;i++){ 26 S[i] = 0; 27 U[i] = D[i] = i; 28 L[i] = i-1; 29 R[i] = i+1; 30 } 31 R[m] = 0, L[0] = m, size = m; 32 for(int i = 1;i <= n; i++) H[i] = -1; 33 } 34 void Link(int r,int c){ 35 ++S[Col[++size]=c]; 36 Row[size] = r; 37 D[size] = D[c]; 38 U[D[c]] = size; 39 U[size] = c; 40 D[c] = size; 41 if(H[r] < 0 ) H[r] = L[size] = R[size] = size; 42 else{ 43 R[size] = R[H[r]]; 44 L[R[H[r]]] = size; 45 L[size] = H[r]; 46 R[H[r]] = size; 47 } 48 } 49 void remove(int c){ 50 L[R[c]] = L[c] , R[L[c]] = R[c]; 51 for(int i = D[c];i != c;i = D[i]) 52 for(int j = R[i];j != i;j = R[j]){ 53 U[D[j]] = U[j] , D[U[j]] = D[j] , --S[Col[j]]; 54 } 55 } 56 void resume(int c){ 57 for(int i = U[c];i != c;i = U[i]) 58 for(int j = L[i];j != i;j = L[j]){ 59 ++S[Col[U[D[j]]=D[U[j]]=j]]; 60 } 61 L[R[c]] = R[L[c]] = c; 62 } 63 bool Dance(int d){ 64 if(R[0] == 0){ 65 for(int i = 0;i < d;i++) g[(ans[i]-1)/9] = (ans[i]-1)%9 + '1';//行和列都是从1开始的 66 for(int i = 0;i < N*N;i++) printf("%c",g[i]);printf("/n"); 67 return true; 68 } 69 int c = R[0]; 70 for(int i = R[0];i != 0;i = R[i]) if(S[i] < S[c]) c = i; 71 remove(c); 72 for(int i = D[c];i != c;i = D[i]){ 73 ans[d] = Row[i]; 74 for(int j = R[i];j != i;j = R[j]) remove(Col[j]); 75 if(Dance(d+1)) return true; 76 for(int j = L[i];j != i;j = L[j]) resume(Col[j]); 77 } 78 resume(c); 79 return false; 80 } 81 }; 82 void place(int &r,int &c1,int &c2,int &c3,int &c4,int i,int j,int k){ 83 r = (i*N+j)*N + k;//N*N*N 循环到这里K,所以就是9宫格都是选K填 84 c1 = i*N+j+1;//从1开始的,0只是个头,这个格子选填K 85 c2 = N*N + i*N + k;//前i行都完成,到这一行的K 86 c3 = N*N*2 + j*N + k;//前j列都完成,到这一列的K 87 c4 = N*N*3 + ((i/3)*3+j/3)*N + k;//前面九宫格都选完了,到这个九宫格选填K 88 } 89 DLX dlx; 90 int main() 91 { 92 while(scanf("%s",g) == 1){ 93 if(strcmp(g,"end") == 0) break; 94 dlx.init(N*N*N,N*N*4);//行:N*N从(1~9)选填,列:每个格子都会有4个列,1:此格子有数字了2:此行有K了3:此列有K了4:这个格子的九宫格有K了 95 int r,c1,c2,c3,c4; 96 for(int i = 0;i < N;i++) 97 for(int j = 0;j < N;j++) 98 for(int k = 1;k <= N;k++) 99 if(g[i*N+j] == '.' || g[i*N+j] == '0' + k){//此格子为空或者已经有K了 100 place(r,c1,c2,c3,c4,i,j,k); 101 dlx.Link(r,c1) , dlx.Link(r,c2) , dlx.Link(r,c3) , dlx.Link(r,c4); 102 } 103 dlx.Dance(0); 104 } 105 return 0; 106 }
View Code
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/288078.html