再遇到一个DLC就刷个专题
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 #include <set> 8 #include <map> 9 #include <string> 10 #include <math.h> 11 #include <stdlib.h> 12 #include <time.h> 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<pair<int,int> >q; 107 q.push(make_pair(sx,sy)); 108 id[sx][sy] = d; 109 while(!q.empty()) 110 { 111 pair<int,int> 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: ",iCase); 181 if(cnt == 0)printf("No solution "); 182 else if(cnt > 1)printf("Multiple Solutions "); 183 else 184 { 185 for(int i = 0;i < N*N;i++) 186 { 187 printf("%c",g[i]); 188 if(i % N == N - 1) 189 printf(" "); 190 } 191 } 192 } 193 return 0; 194 }