本文共 3906 字，大约阅读时间需要 13 分钟。
再遇到一个DLC就刷个专题
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std; 14 const int N = 9; //3*3数独 15 const int MaxN = N*N*N + 10; 16 const int MaxM = N*N*4 + 10; 17 const int maxnode = MaxN*4 + MaxM + 10; 18 char g[MaxN]; 19 int cnt; 20 struct DLX 21 { 22 int n,m,size; 23 int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode]; 24 int H[MaxN],S[MaxM]; 25 int ansd,ans[MaxN]; 26 void init(int _n,int _m) 27 { 28 n = _n; 29 m = _m; 30 for(int i = 0;i <= m;i++) 31 { 32 S[i] = 0; 33 U[i] = D[i] = i; 34 L[i] = i-1; 35 R[i] = i+1; 36 } 37 R[m] = 0; L[0] = m; 38 size = m; 39 for(int i = 1;i <= n;i++)H[i] = -1; 40 } 41 void Link(int r,int c) 42 { 43 ++S[Col[++size]=c]; 44 Row[size] = r; 45 D[size] = D[c]; 46 U[D[c]] = size; 47 U[size] = c; 48 D[c] = size; 49 if(H[r] < 0)H[r] = L[size] = R[size] = size; 50 else 51 { 52 R[size] = R[H[r]]; 53 L[R[H[r]]] = size; 54 L[size] = H[r]; 55 R[H[r]] = size; 56 } 57 } 58 void remove(int c) 59 { 60 L[R[c]] = L[c]; R[L[c]] = R[c]; 61 for(int i = D[c];i != c;i = D[i]) 62 for(int j = R[i];j != i;j = R[j]) 63 { 64 U[D[j]] = U[j]; 65 D[U[j]] = D[j]; 66 --S[Col[j]]; 67 } 68 } 69 void resume(int c) 70 { 71 for(int i = U[c];i != c;i = U[i]) 72 for(int j = L[i];j != i;j = L[j]) 73 ++S[Col[U[D[j]]=D[U[j]]=j]]; 74 L[R[c]] = R[L[c]] = c; 75 } 76 void Dance(int d) 77 { 78 if(cnt > 1)return; 79 if(R[0] == 0) 80 { 81 for(int i = 0;i < d;i++)g[(ans[i]-1)/9] = (ans[i]-1)%9 + '1'; 82 cnt++; 83 return; 84 } 85 int c = R[0]; 86 for(int i = R[0];i != 0;i = R[i]) 87 if(S[i] < S[c]) 88 c = i; 89 remove(c); 90 for(int i = D[c];i != c;i = D[i]) 91 { 92 ans[d] = Row[i]; 93 for(int j = R[i];j != i;j = R[j])remove(Col[j]); 94 Dance(d+1); 95 if(cnt > 1)return; 96 for(int j = L[i];j != i;j = L[j])resume(Col[j]); 97 } 98 resume(c); 99 }100 };101 102 int id[20][20];103 int a[20][20];104 void bfs(int sx,int sy,int d)105 {106 queue >q;107 q.push(make_pair(sx,sy));108 id[sx][sy] = d;109 while(!q.empty())110 {111 pair tmp = q.front();112 int x = tmp.first;113 int y = tmp.second;114 q.pop();115 if(x > 0 && ((a[x][y]%32)/16) == 0)116 if(id[x-1][y] == -1)117 {118 id[x-1][y] = d;119 q.push(make_pair(x-1,y));120 }121 if(x < N-1 && ((a[x][y]%128)/64) == 0)122 if(id[x+1][y] == -1)123 {124 id[x+1][y] = d;125 q.push(make_pair(x+1,y));126 }127 if(y > 0 && ((a[x][y])/128) == 0)128 if(id[x][y-1] == -1)129 {130 id[x][y-1] = d;131 q.push(make_pair(x,y-1));132 }133 if(y < N-1 && ((a[x][y]%64)/32) == 0)134 if(id[x][y+1] == -1)135 {136 id[x][y+1] = d;137 q.push(make_pair(x,y+1));138 }139 }140 }141 DLX dlx;142 143 int main()144 {145 //freopen("in.txt","r",stdin);146 //freopen("out.txt","w",stdout);147 int T;148 scanf("%d",&T);149 int iCase = 0;150 while(T--)151 {152 iCase++;153 for(int i = 0;i < N;i++)154 for(int j = 0;j < N;j++)155 scanf("%d",&a[i][j]);156 memset(id,-1,sizeof(id));157 int index = 0;158 for(int i = 0;i < N;i++)159 for(int j = 0;j < N;j++)160 if(id[i][j] == -1)161 bfs(i,j,++index);162 dlx.init(N*N*N,N*N*4);163 for(int i = 0;i < N;i++)164 for(int j = 0;j < N;j++)165 for(int k = 1;k <= N;k++)166 {167 if(a[i][j]%16 != 0 && a[i][j]%16 != k)continue;168 int r = (i*N+j)*N + k;169 int c1 = i*N+j+1;170 int c2 = N*N+i*N+k;171 int c3 = N*N*2+j*N+k;172 int c4 = N*N*3+(id[i][j]-1)*N+k;173 dlx.Link(r,c1);174 dlx.Link(r,c2);175 dlx.Link(r,c3);176 dlx.Link(r,c4);177 }178 cnt = 0;179 dlx.Dance(0);180 printf("Case %d:\n",iCase);181 if(cnt == 0)printf("No solution\n");182 else if(cnt > 1)printf("Multiple Solutions\n");183 else184 {185 for(int i = 0;i < N*N;i++)186 {187 printf("%c",g[i]);188 if(i % N == N - 1)189 printf("\n");190 }191 }192 }193 return 0;194 }
转载于:https://www.cnblogs.com/cnblogs321114287/p/4729990.html