dancing links

题目链接:跳舞链

精准覆盖:

struct node
{
    int x,y;
    int l,r,u,d;
    node(int x=0,int y=0,int l=0,
         int r=0,int u=0,int d=0):
        x(x),y(y),l(l),r(r),u(u),d(d) {}
} dl[10105];

int a[105][105],id[105][105];
int idx,one[105];

void build(int n,int m)
{
    dl[0]=node(0),idx=m;
    for(int j=1; j<=m; j++)
    {
        dl[j]=node(0,j,j-1,dl[j-1].r,j,j);
        dl[dl[j-1].r].l=j,dl[j-1].r=j;
        int pre=j;
        for(int i=1; i<=n; i++)
            if(a[i][j]==1)
            {
                int x=(id[i][j]=++idx);
                dl[idx]=node(i,j,idx,idx);
                dl[x].d=dl[pre].d,dl[x].u=pre;
                dl[dl[pre].d].u=x,dl[pre].d=x;
                pre=x,one[j]++;
            }
    }
    for(int i=1; i<=n; i++)
    {
        int pre=0;
        for(int j=1; j<=m; j++)
            if(a[i][j]==1)
                if(!pre)pre=id[i][j];
                else
                {
                    int x=id[i][j];
                    dl[x].r=dl[pre].r,dl[x].l=pre;
                    dl[dl[pre].r].l=x,dl[pre].r=x;
                    pre=x;
                }
    }
}

void change(int x,bool op)
{
    dl[dl[x].r].l=op?x:dl[x].l;
    dl[dl[x].l].r=op?x:dl[x].r;
    for(int i=dl[x].d;i!=x;i=dl[i].d)
        for(int j=dl[i].r;j!=i;j=dl[j].r)
        {
            dl[dl[j].d].u=op?j:dl[j].u;
            dl[dl[j].u].d=op?j:dl[j].d;
            if(op)one[dl[j].y]++;
            else one[dl[j].y]--;
        }
}

int ans[105];

bool dancing(int depth)
{
    int x=dl[0].r;
    if(x==0)return true;
    if(dl[x].d==x)return false;
    for(int i=x;i;i=dl[i].r)
        if(one[i]<one[x])x=i;
    change(dl[x].y,0);
    for(int i=dl[x].d;i!=x;i=dl[i].d)
    {
        ans[depth]=dl[i].x;
        for(int j=dl[i].r;j!=i;j=dl[j].r)
            change(dl[j].y,0);
        if(dancing(depth+1))return true;
        for(int j=dl[i].l;j!=i;j=dl[j].l)
            change(dl[j].y,1);
    }
    change(dl[x].y,1);
    return false;
}

void init(void)
{
    memset(id,0,sizeof(id));
    memset(dl,0,sizeof(dl));
    memset(one,0,sizeof(one));
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                scanf("%d",&a[i][j]);
        build(n,m);
        if(dancing(1))
            printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

题目链接:数独

dancing links:

struct node
{
    int x,y;
    int l,r,u,d;
    node(int x=0,int y=0,int l=0,
         int r=0,int u=0,int d=0):
        x(x),y(y),l(l),r(r),u(u),d(d) {}
} dl[242550];

int a[735][330],id[735][330];
int idx,one[330],ans[85];

void build(int n,int m)
{
    dl[0]=node(0),idx=m;
    for(int j=1; j<=m; j++)
    {
        dl[j]=node(0,j,j-1,dl[j-1].r,j,j);
        dl[dl[j-1].r].l=j,dl[j-1].r=j;
        int pre=j;
        for(int i=1; i<=n; i++)
            if(a[i][j]==1)
            {
                int x=(id[i][j]=++idx);
                dl[idx]=node(i,j,idx,idx);
                dl[x].d=dl[pre].d,dl[x].u=pre;
                dl[dl[pre].d].u=x,dl[pre].d=x;
                pre=x,one[j]++;
            }
    }
    for(int i=1; i<=n; i++)
    {
        int pre=0;
        for(int j=1; j<=m; j++)
            if(a[i][j]==1)
                if(!pre)pre=id[i][j];
                else
                {
                    int x=id[i][j];
                    dl[x].r=dl[pre].r,dl[x].l=pre;
                    dl[dl[pre].r].l=x,dl[pre].r=x;
                    pre=x;
                }
    }
}

inline void change(int x,bool op)
{
    dl[dl[x].r].l=op?x:dl[x].l;
    dl[dl[x].l].r=op?x:dl[x].r;
    for(int i=dl[x].d; i!=x; i=dl[i].d)
        for(int j=dl[i].r; j!=i; j=dl[j].r)
        {
            dl[dl[j].d].u=op?j:dl[j].u;
            dl[dl[j].u].d=op?j:dl[j].d;
            if(op)one[dl[j].y]++;
            else one[dl[j].y]--;
        }
}

bool dancing(int depth)
{
    int x=dl[0].r;
    if(x==0)return true;
    if(dl[x].d==x)return false;
    for(int i=x; i; i=dl[i].r)
        if(one[i]<one[x])x=i;
    change(dl[x].y,0);
    for(int i=dl[x].d; i!=x; i=dl[i].d)
    {
        ans[depth]=dl[i].x;
        for(int j=dl[i].r; j!=i; j=dl[j].r)
            change(dl[j].y,0);
        if(dancing(depth+1))return true;
        for(int j=dl[i].l; j!=i; j=dl[j].l)
            change(dl[j].y,1);
    }
    change(dl[x].y,1);
    return false;
}

int sk[10][10],row=0;

inline int block(int x,int y)
{
    int b=1;
    for(int i=1; i<=9; i+=3)
        for(int j=1; j<=9; j+=3,b++)
            if(i<=x && x<=i+2
                    &&j<=y && y<=j+2)
                return b;
}

struct point
{
    int x,y,val;
    point(int x=0,int y=0,int val=0):
        x(x),y(y),val(val) {}
}p[735];

inline int put(int x,int y,int val)
{
    a[++row][9*(x-1)+y]=1;
    a[row][9*(x-1)+val+81]=1;
    a[row][9*(y-1)+val+162]=1;
    a[row][9*(block(x,y)-1)+val+243]=1;
    p[row]=point(x,y,val);
}

inline void init(void)
{
    idx=row=0;
    memset(a,0,sizeof(a));
    memset(id,0,sizeof(id));
    memset(dl,0,sizeof(dl));
    memset(one,0,sizeof(one));
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        for(int i=1; i<=9; i++)
            for(int j=1; j<=9; j++)
            {
                scanf("%d",&sk[i][j]);
                if(sk[i][j])
                    put(i,j,sk[i][j]);
                else
                    for(int k=1;k<=9;k++)
                        put(i,j,k);
            }
        build(row,324);
        dancing(1);
        for(int i=1;i<=81;i++)
            sk[p[ans[i]].x][p[ans[i]].y]=p[ans[i]].val;
        for(int i=1;i<=9;i++)
            for(int j=1;j<=9;j++)
            {
                printf("%d",sk[i][j]);
                if(j!=9)printf(" ");
                else printf("\n");
            }
    }
    return 0;
}