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
*/