Skip to content

Dancing Links X

应用：解决精确覆盖问题。

例如数独，k皇后等涉及同一个数在一定范围内值出现一次的问题可以用DLX解决。

模板

P4929

  • 注意：

1.每次删除和恢复的都是表头下面的一整列以及含有1的一整行，而整个过程中更改的只有表头左右指针和不是表头那列的1的上下指针

（因为恢复要从表头向下访问，再从行头向右访问）。

只有这样才能实现访问到已删除的1。

2.十字链表中上下，左右的顺序无所谓，但必须统一。

3.注意所有链表都是双向，即是一个环。当自己指向自己时为空。

4.算法判定结果错误的依据是表头还有剩余，但元素都删完了，说明之前有两个以上的1冲突。

5.删除时更改上下元素的之中呢一定注意顺序。

    f[++cnt].u=C;
    f[cnt].d=f[C].d;
    f[f[C].d].u=cnt;
    f[C].d=cnt;
    f[cnt].row=R;
    f[cnt].col=C;

6.每次选用1个数最小的列实际也是剪枝优化，为了让更多的1在当前回合就被筛掉，以减少搜索次数。

7.去除元素时是去除除了表头元素意外所有下面的1，和除了行头外所有1.为了下次从表头，行头访问到被删除的点。 code time:

1) 数组版： 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=550,M=N*N+N;
int n,m,cnt;
int d[M],u[M],l[M],r[M],row[M],col[M];
int s[M],h[M],ans[M];


void init(){
    for(int i=0;i<=m;++i){
        l[i]=i-1;
        r[i]=i+1;
        u[i]=d[i]=i;
    }
    r[m]=0;
    l[0]=m;//链表头尾特判
    memset(h,-1,sizeof h);
    memset(s,0,sizeof s);
    cnt=m+1;
}

void add(int R,int C){
    s[C]++;
    row[cnt]=R;
    col[cnt]=C;
    u[cnt]=C;
    d[cnt]=d[C];
    u[d[C]]=cnt;
    d[C]=cnt;//注意顺序！

    if(h[R]==-1){
        h[R]=l[cnt]=r[cnt]=cnt;
    }else{
        r[cnt]=h[R];
        l[cnt]=l[h[R]];
        r[l[h[R]]]=cnt;
        l[h[R]]=cnt;//顺序
    }
    cnt++;
}

void remove(int C){
    r[l[C]]=r[C],l[r[C]]=l[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=d[C];i!=C;i=d[i]){
        for(int j=r[i];j!=i;j=r[j]){
            u[d[j]]=j;
            d[u[j]]=j;//再接回来
            s[col[j]]++;
        }
    }
    l[r[C]]=C,r[l[C]]=C;
}

void print1(int tot){
    for(int i=0;i<tot;++i)printf("%d ",ans[i]);
}
int dfs(int dep){
    if(r[0]==0){
        print1(dep);
        return 1;//一个解就退出
    }
    int c=r[0];
    for(int i=r[0];i!=0;i=r[i]){
        if(s[i]<s[c])c=i;
    }//剪枝优化
    remove(c);//去除当前表头下那列（C'）的所有1，表示已经被纳入选择。
    for(int i=d[c];i!=c;i=d[i]){
        ans[dep]=row[i];//选择当前行。
        for(int j=r[i];j!=i;j=r[j])remove(col[j]);//去除除了C'以外的当前行的1
        if(dfs(dep+1))return 1;
        for(int j=r[i];j!=i;j=r[j])resume(col[j]);
    }
    resume(c);//回溯
    return 0;//无解
}
int read1(){
    int x=0;
    char ch=getchar();
    while(ch>'9' || ch<'0'){
        ch=getchar();
    }
    while(ch<='9' && ch>='0'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x;
}
int main(){
    n=read1(),m=read1();
    init();
    for(int i=1;i<=n;++i){
        for(int j=1,tmp;j<=m;++j){
            tmp=read1();
            if(tmp)add(i,j);
        }
    }
    if(!dfs(0))printf("No Solution!");
    return 0;
}
2) 结构体版： 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=550,M=N*N;
int n,m,cnt;
int s[M],h[M],ans[M];
struct node{
    int u,d,l,r,row,col;
}f[M];
void init(){
    for(int i=0;i<=m;++i){
        f[i].l=i-1;
        f[i].r=i+1;
        f[i].u=f[i].d=i;
    }
    f[m].r=0;
    f[0].l=m;
    cnt=m;
    memset(h,-1,sizeof h);
    memset(s,0,sizeof s);
}
void link(int R,int C){
    s[C]++;
    f[++cnt].u=C;
    f[cnt].d=f[C].d;
    f[f[C].d].u=cnt;
    f[C].d=cnt;
    f[cnt].row=R;
    f[cnt].col=C; 

    if(h[R]==-1){
        h[R]=f[cnt].l=f[cnt].r=cnt;
    }else{
        f[cnt].l=h[R];
        f[cnt].r=f[h[R]].r;
        f[f[h[R]].r].l=cnt;
        f[h[R]].r=cnt;
    }

}
void remove(int C){
    f[f[C].r].l=f[C].l,f[f[C].l].r=f[C].r;
    for(int i=f[C].d;i!=C;i=f[i].d){
        for(int j=f[i].r;j!=i;j=f[j].r){
            f[f[j].d].u=f[j].u;
            f[f[j].u].d=f[j].d;
            s[f[j].col]--;
        }
    }
}
void resume(int C){
    for(int i=f[C].d;i!=C;i=f[i].d){
        for(int j=f[i].r;j!=i;j=f[j].r){
            f[f[j].d].u=j;
            f[f[j].u].d=j;
            s[f[j].col]++;
        }
    }
    f[f[C].l].r=C,f[f[C].r].l=C;
}
void print1(int tot){
    for(int i=1;i<=tot;++i)printf("%d ",ans[i]);
}
int dfs(int dep){
    if(f[0].r==0){
        print1(dep-1);
        return 1;
    }
    int c=f[0].r;
    for(int i=f[0].r;i!=0;i=f[i].r)if(s[i]<s[c])c=i;
    remove(c);
    for(int i=f[c].d;i!=c;i=f[i].d){
        ans[dep]=f[i].row;
        for(int j=f[i].r;j!=i;j=f[j].r)remove(f[j].col);
        if(dfs(dep+1))return 1;
        for(int j=f[i].r;j!=i;j=f[j].r)resume(f[j].col);
    }
    resume(c);
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    init();
    for(int i=1;i<=n;++i){
        for(int j=1,tmp;j<=m;++j){
            scanf("%d",&tmp);
            if(tmp)link(i,j);
        }
    }   
    if(!dfs(1))printf("No Solution!");
    return 0;
}