精准覆盖:
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;
}
