首页 > 代码库 > POJ 3076 Sudoku (dancing links)
POJ 3076 Sudoku (dancing links)
题目大意:
16*16的数独。
思路分析:
多说无益.
想说的就是dancing links 的行是按照
第一行第一列填 1
第一行第二列填 2
……
第一行第十五列填15
第一行第二列填 1
……
第二行。。。。
列的纺织则是
第一行放1,第一行放2,。。第十六行放16.。。第一列放1.。第一列放2.。。第十六列放16.。第一块区域放1 。。。。然后在最后81位就是放自己的位置,准确的说就是 r*m+c。
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define maxn 16*16*16*16*16*4+5 #define inf 0x3f3f3f3f using namespace std; int n=16*16*9,m=16*16*4,p; int map[16*16*16+5][16*16*4+5]; int L[maxn],R[maxn],D[maxn],U[maxn],S[maxn],O[maxn],col[maxn],row[maxn],head,cnt; int num; void dancing_links_init() { head=0; memset(S,0,sizeof S); for(int i=head;i<=m;i++) { R[i]=(i+1)%(m+1); L[i]=(i-1+m+1)%(m+1); U[i]=D[i]=i; } cnt=m+1; for(int i=1;i<=n;i++) { int rowh=-1; for(int j=1;j<=m;j++) { if(map[i][j]) { S[j]++; U[cnt]=U[j]; D[U[j]]=cnt; U[j]=cnt; D[cnt]=j; row[cnt]=i; col[cnt]=j; if(rowh==-1) { L[cnt]=R[cnt]=cnt; rowh=cnt; } else { L[cnt]=L[rowh]; R[L[rowh]]=cnt; R[cnt]=rowh; L[rowh]=cnt; } cnt++; } } } } void Remove(const 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(const int &c) { for(int i=U[c];i!=c;i=U[i]) { for(int j=L[i];j!=i;j=L[j]) { ++S[col[j]]; U[D[j]]=j; D[U[j]]=j; } } L[R[c]]=c; R[L[c]]=c; } bool dfs(const int &k)//可行解 { if(head==R[head]) { sort(O,O+256); for(int i=0;i<256;i++) { printf("%c",O[i]-i*16+'A'-1); if(i%16==15)puts(""); } puts(""); return true; } int mx=inf,cur=0; for(int t=R[head];t!=head;t=R[t]) { if(S[t]<mx) { mx=S[t]; cur=t; } } Remove(cur);//根据开始的时候的判断条件,可以知道是一列一列的选择 for(int i=D[cur];i!=cur;i=D[i])//这里就是先选择列 {//然后去选择删除哪一行是覆盖了这列的 O[k]=row[i]; for(int j=R[i];j!=i;j=R[j]) { Remove(col[j]); } if(dfs(k+1))return true; for(int j=L[i];j!=i;j=L[j]) { Resume(col[j]); } } Resume(cur); return false; } /* void dfs(const int &k)//最优解 { if(R[head]==head) { if(k<num)num=k; return; } if(k>=num)return; int mx=inf,cur=0; for(int t=R[head];t!=head;t=R[t]) { if(S[t]<mx) { mx=S[t]; cur=t; } } Remove(cur); for(int i=D[cur];i!=cur;i=D[i]) { for(int j=R[i];j!=i;j=R[j]) { Remove(col[j]); } dfs(k+1); for(int j=L[i];j!=i;j=L[j]) { Resume(col[j]); } } Resume(cur); } */ char tmp[16][1111]; char str[1111]; int main() { while(scanf("%s",tmp[0])!=EOF) { for(int i=1;i<16;i++)scanf("%s",tmp[i]); int cnt=0; for(int i=0;i<16;i++) for(int j=0;j<16;j++) str[cnt++]=tmp[i][j]; memset(map,0,sizeof map); int len=cnt; for(int i=0;i<len;i++) { int r=i/16; int c=i-r*16; int base=(r*16+c)*16; if(str[i]=='-') { for(int k=1;k<=16;k++) { map[base+k][r*16+k]=1; map[base+k][256+c*16+k]=1; map[base+k][256+256+16*(4*(r/4)+(c/4))+k]=1; map[base+k][256*3+r*16+c+1]=1; } } else { int k=str[i]-'A'+1; map[base+k][r*16+k]=1; map[base+k][256+c*16+k]=1; map[base+k][256+256+16*(4*(r/4)+(c/4))+k]=1; map[base+k][256+256+256+r*16+c+1]=1; } } dancing_links_init(); dfs(0); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。