[kuangbin带你飞]专题三 Dancing Links

Dancing Links 是一种数据结构，用于精确覆盖。详情去下面链接学；感谢大牛总结。

学习资料： http://www.cnblogs.com/grenet/p/3145800.html http://blog.csdn.net/mu399/article/details/7627862

F - SudokuPOJ - 3074 

题意：就是给你一个随机的九宫格，问你答案是多少？

算法：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 }