[DLX]HDOJ4069 Squiggly Sudoku

题意：有9*9的格子

每个格子由五部分组成：上(16)、右(32)、下(64)、左(128)、和该格的数值(0~9)

若上下左右有分割格子的线就加上相应的数，该格的数值若为0，则是未知 1~9 则是已知

然后根据分割线做数独(每行、每列、每宫都是1~9)

输出无解、多解或者一个解就输出那个解

这种数独与普通3*3的数独的唯一区别就是宫的划分的方式不一样

16、32、64、128这几个数很特殊分别是$2^4$、$2^5$、$2^6$、$2^7$

也就是相应的二位数，若第4位为1，则上面有分割线

　　　　　　　　　　若第5位为1，则右边有分割线

　　　　　　　　　　若第6位为1，则下面有分割线

　　　　　　　　　　若第7位为1，则左边有分割线

那么只要随便dfs一下确定在哪个宫里就好啦

然后把模板里本来宫的位置是(i/3)*3+(j/3) 换成 dfs搜出来的宫的位置就好啦~

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 //const int N=2e5+5;

 const int N=; //3*3数独

 const int MaxN=N*N*N+;    // 一格能填9个数  9*9格

 const int MaxM=N*N*+;     // 9*9*4=(9+9+9)*9+9*9    (9+9+9)是9行 9列 9格 *9是9个数 9*9是81个格子

 const int maxnode=MaxN*+MaxM+;

 int g[MaxN];

 int anss;

 struct DLX

 {

     int n, m, size;

     int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode];

     int H[MaxN], S[MaxM];  // S: 各列节点数

     int ansd, ans[MaxN];

     void init(int _n, int _m)

     {

         n=_n;

         m=_m;

         for(int i=; i<=m; i++)

         {

             S[i]=;         //每一列元素个数

             U[i]=D[i]=i;//上下指针

             L[i]=i-;      //←

             R[i]=i+;     //→

         }

         R[m]=;          //循环 最后一个指向第一个

         L[]=m;           //第一个往前指向最后一个

         size=m;           // 节点总数

         for(int i=; i<=n; i++)

             H[i]=-;     //头指针

     }

     void Link(int r, int c)

     {

         S[Col[++size]=c]++;

         Row[size]=r;

         D[size]=D[c];

         U[D[c]]=size;

         U[size]=c;

         D[c]=size;

         if(H[r]<)

             H[r]=L[size]=R[size]=size;

         else

         {

             R[size]=R[H[r]];

             L[R[H[r]]]=size;

             L[size]=H[r];

             R[H[r]]=size;

         }

     }

     void remove(int c)

     {

         L[R[c]]=L[c];

         R[L[c]]=R[c];

         for(int i=D[c]; i!=c; i=D[i])

             for(int j=R[i]; j!=i; j=R[j])

             {

                 U[D[j]]=U[j];

                 D[U[j]]=D[j];

                 S[Col[j]]--;

             }

     }

     void resume(int c)

     {

         for(int i=U[c]; i!=c; i=U[i])

             for(int j=L[i]; j!=i; j=L[j])

                 S[Col[U[D[j]]=D[U[j]]=j]]++;

         L[R[c]]=R[L[c]]=c;

     }

     void Dance(int d)

     {

         if(anss>)

             return ;

         if(R[]==)

         {

             for(int i=;i<d;i++)

                 g[(ans[i]-)/N]=(ans[i]-)%N+;

             anss++;

         }

         int c=R[];

         for(int i=R[]; i!=; i=R[i])

             if(S[i]<S[c])

                 c=i;

         remove(c);

         for(int i=D[c]; i!=c; i=D[i])

         {

             ans[d]=Row[i];

             for(int j=R[i]; j!=i; j=R[j])

                 remove(Col[j]);

             Dance(d+);

             for(int j=L[i]; j!=i; j=L[j])

                 resume(Col[j]);

         }

         resume(c);

     }

 } dlx;

 int s[][];

 int vis[][];

 void dfs(int x,int y,int col)

 {

     if(x<||x>=||y<||y>=||vis[x][y]!=-)

         return ;

     if((s[x][y]&(<<))==)

     {

         vis[x][y]=col;

         dfs(x,y-, col);

     }

     if((s[x][y]&(<<))==)

     {

         vis[x][y]=col;

         dfs(x+,y, col);

     }

     if((s[x][y]&(<<))==)

     {

         vis[x][y]=col;

         dfs(x,y+, col);

     }

     if((s[x][y]&(<<))==)

     {

         vis[x][y]=col;

         dfs(x-,y, col);

     }

 }

 void palce(int &r, int &c1, int &c2, int &c3, int &c4, int i, int j, int k)

 {

     r=(i*N+j)*N+k;  // 第几行

     c1=i*N+j+;     //  第几个格子

     c2=N*N+i*N+k;   // 第i行上的k

     c3=N*N*+j*N+k; // 第j列上的k

     c4=N*N*+(vis[i][j])*N+k; // 某宫中的k;

 }

 int main()

 {

     int t, ca=;

     scanf("%d", &t);

     while(t--)

     {

         for(int i=;i<N;i++)

             for(int j=;j<N;j++)

                 scanf("%d", &s[i][j]);

         int num=;

         memset(vis, -, sizeof(vis));

         for(int i=;i<N;i++)

             for(int j=;j<N;j++)

             {

                 if(vis[i][j]==-)

                     dfs(i, j, num++);

                 if((s[i][j]-(<<))>=)

                     s[i][j]-=<<;

                 if((s[i][j]-(<<))>=)

                     s[i][j]-=<<;

                 if((s[i][j]-(<<))>=)

                     s[i][j]-=<<;

                 if((s[i][j]-(<<))>=)

                     s[i][j]-=<<;

             }

         dlx.init(N*N*N, *N*N);

         for(int i=; i<N; i++)

             for(int j=; j<N; j++)

                 for(int k=; k<=; k++)

                     if(s[i][j]== || s[i][j]==k)

                     {

                         int r, c1, c2, c3, c4;

                         palce(r, c1, c2, c3, c4, i, j, k);

                         dlx.Link(r, c1);

                         dlx.Link(r, c2);

                         dlx.Link(r, c3);

                         dlx.Link(r, c4);

                     }

         anss=;

         dlx.Dance();

         printf("Case %d:\n", ca++);

         if(anss==)

             puts("No solution");

         else if(anss>)

             puts("Multiple Solutions");

         else

         {

             for(int i=;i<N;i++)

             {

                 for(int j=;j<N;j++)

                     printf("%d", g[i*N+j]);

                 puts("");

             }

         }

     }

     return ;

 }

HDOJ 4069

巴特西

[DLX]HDOJ4069 Squiggly Sudoku

最新文章

热门文章