特别作死地强行用DLX搞靶形数独。。。在经历了一个星期种种挫折及崩溃之后，顺带找了各种模板，终于把它AC了。。。（虽然代码冗长而复杂） 而且特别坑的是最后卡了好几十分钟的地方只是数组的数的位置错了！！！！！！简直是mmp
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int const maxn = 10010; int n,m,inf1=81,inf2=162,inf3=243,inf4=324; int num,mmax=-1; char s[10][10]; int G[10][10]; int Score[10][10]={{0,0,0,0,0,0,0,0,0,0},//!!!!!!!!!!!!!!!!!!!!!!!!!!!!! {0,6,6,6,6,6,6,6,6,6}, {0,6,7,7,7,7,7,7,7,6}, {0,6,7,8,8,8,8,8,7,6}, {0,6,7,8,9,9,9,8,7,6}, {0,6,7,8,9,10,9,8,7,6}, {0,6,7,8,9,9,9,8,7,6}, {0,6,7,8,8,8,8,8,7,6}, {0,6,7,7,7,7,7,7,7,6}, {0,6,6,6,6,6,6,6,6,6}}; struct DLX{ int n,m,size; int U[maxn],D[maxn],R[maxn],L[maxn],col[maxn],row[maxn]; int H[maxn];//行头结点 int S[maxn];//列头结点 int ansd,ans[maxn],get[maxn]; void in_it(int _n){ n=_n; memset(H,-1,sizeof(H)); for(int i=0;i<=n;i++){ S[i]=0; U[i]=i; D[i]=i;//初始状态下，上下指向自己 R[i]=i+1;//右边的指针指向右边一个数 L[i]=i-1;//左边的指针指向左边一个数 } R[n]=0;L[0]=n;//最左边和最右边的数应该是连起来的，所以左指向最后一个数，最右一个数指向最左边 size=n;//编号，每一列都应该有一个头结点，编号1-m }//附初始值 void link(int r,int l){//将第r行，第l列的节点加入 size++; S[l]++;//第size个节点所在的列为l，则当前列的节点数++；(注意：size是从m开始编号的) row[size]=r;//第size个节点的行位置为r col[size]=l; U[size]=U[l];//这个节点上面的指针就指向这一列 D[size]=l;//当前节点的下面的指针指向当前这一列所能指向的最低位置 D[U[l]]=size;//当前这一列的最低位置指向该节点 U[l]=size;//当前这一列的最低位置所能指向的最高位置就是这个节点 if(~H[r]){//如果这个点是这一行最先加入的节点 L[size]=L[H[r]]; R[size]=H[r];//左右的指针都指向这个节点 L[R[size]]=size; R[L[size]]=size; } else { H[r]=L[size]=R[size]=size; } } void remove(int c){//删除节点c，以及c上下节点所在的行，每次调用这个函数，都是从列头节点开始向下删除，固c也可以理解为第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){//恢复节点c for(int i=U[c];i!=c;i=U[i]){ for(int j=L[i];j!=i;j=L[j]){ S[col[j]]++; D[U[j]]=j; U[D[j]]=j; } }//直接将左右上下节点掠过这个点连旁边的点就算删除了 R[L[c]]=c; L[R[c]]=c; } void dance(int d,int score){//递归深度 if(R[0]==0){//已经没有元素未被覆盖了 mmax=max(mmax,score); return ; } int c=R[0]; for(int i=R[0];i!=0;i=R[i]) if(S[i]<S[c]) c=i; remove(c);//找到节点数最少的列，当前元素不是原图上0，1的节点，而是列头节点 for(int i=D[c];i!=c;i=D[i]){ int tmp=row[i]; for(int j=R[i];j!=i;j=R[j]) remove(col[j]); int key=(tmp-1)%9+1; int z=(tmp-1)/9/9+1; int y=(tmp-1)/9%9+1; int mm=key*Score[z][y]; dance(d+1,score+mm); for(int j=L[i];j!=i;j=L[j])//没有找到，删除这个节点，重新找 resume(col[j]); } resume(c); } void build(){ for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ scanf("%d",&G[i][j]); } } for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(G[i][j]!=0){ int r=(i*9+j)*9+G[i][j]; int c1=i*9+j+1; int c2=inf1+i*9+G[i][j]; int c3=inf2+j*9+G[i][j]; int c4=inf3+((i/3)*3+(j/3))*9+G[i][j]; link(r,c1); link(r,c2); link(r,c3); link(r,c4); S[c1]=-1; S[c2]=-1; S[c3]=-1; S[c4]=-1; } } } for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(G[i][j]==0){ for(int k=1;k<=9;k++){ int r=(i*9+j)*9+k; int c1=i*9+j+1; int c2=inf1+i*9+k; int c3=inf2+j*9+k; int c4=inf3+((i/3)*3+(j/3))*9+k; if(~S[c1]&&~S[c2]&&~S[c3]&&~S[c4]){ link(r,c1); link(r,c2); link(r,c3); link(r,c4); } } } } } } }x; int main(){ x.in_it(324); x.build(); x.dance(0,0); printf("%d",mmax); return 0; }AC的那一刻我觉得自己已经升华了…… （虽然不知道自己的理解有没有问题，真的是强行用DLX）
