Dancing links算法

Dancing Links算法由Knuth设计并命名，用于解决精确覆盖问题。 这样的问题就是，给定一个01矩阵，要求挑出它的若干行，组成的子矩阵满足条件：每一列恰有一个1。 解决的办法是把矩阵的每一行每一列的非零元1用双十字链表结构链接起来，方便删除和回溯。然后依次尝试每一种可能的情形。 具体参见原文。

#include<iostream>
#include<stdlib.h>
#include <conio.h>
#include <time.h>
using namespace std;

const int N=60009;
const int M=70;

int data[N][M];
int S[N];
int R[N][M];
int L[N][M];
int U[N][M];
int D[N][M];

int col;
int row;
int res[N];

void cover(int c)
{
    int i,j;
    L[0][R[0][c]]=L[0][c];
    R[0][L[0][c]]=R[0][c];
    for(i=D[0][c];i!=0;i=D[i][c])
    {
        for(j=R[i][c];j!=c;j=R[i][j])
        {
            U[D[i][j]][j]=U[i][j];
            D[U[i][j]][j]=D[i][j];
            S[j]--;

        }
    }

}

void uncover(int c)
{
    int i,j;
    for(i=U[0][c];i!=0;i=U[i][c])
    {
        for(j=L[i][c];j!=c;j=L[i][j])
        {
            S[j]++;
            D[U[i][j]][j]=i;
            U[D[i][j]][j]=i;
        }
    }
    L[0][R[0][c]]=c;
    R[0][L[0][c]]=c;

}

void search(int n)
{
    int i,j,c,r;
    c=R[0][0];
    for(i=R[0][0];i!=0;i=R[0][i])
    {
        if(S[i]<S[c])
            c=i;
    }

    if(c==0)
    {
        for(i=0;i<n;i++)
            cout<<res[i]<<'t';
        cout<<endl;
        for(j=0;j<n;j++)
        {
            for(i=1;i<=col;i++)
                cout<<data[res[j]][i];
            cout<<endl;
        }

    }
    else
    {
        cover(c);
        for(r=D[0][c];r!=0;r=D[r][c])
        {
            for(j=R[r][c];j!=c;j=R[r][j])
            {
                cover(j);
            }
            res[n]=r;
            search(n+1);
            for(j=L[r][c];j!=c;j=L[r][j])
            {
                uncover(j);
            }
        }
        uncover(c);
    }
}
void init()
{
    int i,j;
    int tmp;
    srand((unsigned)time(NULL));
    for(i=1;i<=row;i++)
    {
        for(j=1;j<=col;j++)
        {

        //  data[i][j]=rand()%2;
            cin>>data[i][j];
            if(data[i][j]==1)
                S[j]++;
        }

    }
    for(i=0;i<=col;i++)
    {
        L[0][i]=(i+col)%(col+1);
        R[0][i]=(i+1)%(col+1);
    }
    for(i=1;i<=row;i++)
    {
        tmp=0;
        for(j=1;j<=col;j++)
        {
            if(data[i][j]==1)
            {
                R[i][tmp]=j;
                L[i][j]=tmp;
                tmp=j;
            }
        }
        R[i][tmp]=R[i][0];
        L[i][R[i][0]]=tmp;

    }
    for(i=1;i<=col;i++)
    {
        tmp=0;
        for(j=1;j<=row;j++)
        {
            if(data[j][i]==1)
            {
                U[j][i]=tmp;
                D[tmp][i]=j;
                tmp=j;
            }
        }
        D[tmp][i]=0;
        U[0][i]=tmp;
    }

}
int main()
{
    cin>>row>>col;
    init();
    search(0);
    return 0;
}
/*
0 0 1 0 1 1 0
1 0 0 1 0 0 1
0 1 1 0 0 1 0
1 0 0 1 0 0 0
0 1 0 0 0 0 1
0 0 0 1 1 0 1
*/