题目来源：http://poj.org/problem?id=3074 ★我是真滴菜，这题又搞了三天，最后又是一个小细节问题。但愿这次之后真正理解了舞蹈链
题意：
有一个9x9的矩阵，有些位置的数字已经确定了下来，但还有很多地方没确定。现在你要找到一个满足如下条件的填数字的方法，然后输入最终填完的矩阵 ①：每个单元有且仅有一个数字 ②：每一列包含了1-9的9个数字 ③：每一行包含了1-9的9个数字 ④：将矩阵划分为9块，每一块都包含了1-9的9个数字
思路：
这题可以用 舞蹈链求精确覆盖，由于模板题在HUSTOJ上但是不能提交了，我也没写过模板题，导致卡了三天，不过现在大概是清楚了
先把模型转化成舞蹈链
题目给了4个约束条件，我们可以顺藤摸瓜，将约束条件转化成列，根据题意很容易知道，必须 找到一系列的行使得 所有的列上都有且仅有一个1 那么那些行就是答案了 约束条件①：( x , y )单元被填过了 代表第p1列 int p1=(x-1)*9+y; 约束条件②：第x行有一个数字v 代表第p2列 int p2=(x-1)*9+v+81; 约束条件③：第y列有一个数字v 代表第p3列 int p3=(y-1)*9+v+81*2; 约束条件④：第tmp块有一个数字v 代表第p4列 int tmp=((x-1)/3)*3+(y-1)/3+1; int p4=(tmp-1)*9+v+81*3;
至于行，就是每一个单元放什么数字咯~
得出答案
我们dance之后会得到很多行，但是这些行并不能直接得到题目要求的答案 我们不妨保存一个get数组记录每一行代表的意义（坐标以及数字），然后就好解决了
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<string>
#define ls k<<1,l,mid
#define rs k<<1|1,mid+1,r
using namespace std
;
const int N
=81*9*4+81*4+10;
const int M
=81*4+10;
const int inf
=0x7fffffff;
const int mod
=1e9+7;
const double eps
=1e-8;
const double pi
=acos(-1);
typedef long long LL
;
template<class T>
void read(T
&x
)
{
char c
; x
=1;
while((c
=getchar())<'0'||c
>'9') if(c
=='-') x
=-1;
T res
=c
-'0';
while((c
=getchar())>='0'&&c
<='9') res
=res
*10+c
-'0';
x
*=res
;
}
struct DLX
{
int n
,m
,cnt
;
int up
[N
],down
[N
],left
[N
],right
[N
],col
[N
];
int sz
[M
],head
[M
<<1],get
[N
][3],ans
[100];
void init(int nn
,int mm
)
{
n
=nn
; m
=mm
;
for(int i
=0;i
<=m
;i
++){
up
[i
]=down
[i
]=i
;
right
[i
]=i
+1;
left
[i
]=i
-1;
}
right
[m
]=0; left
[0]=m
;
cnt
=m
;
memset(head
,-1,sizeof head
);
memset(sz
,0,sizeof sz
);
}
void link(int r
,int c
,int x
,int y
,int v
)
{
cnt
++;
col
[cnt
]=c
;
sz
[c
]++;
up
[cnt
]=up
[c
];
down
[cnt
]=c
;
down
[up
[c
]]=cnt
;
up
[c
]=cnt
;
get
[cnt
][0]=x
; get
[cnt
][1]=y
; get
[cnt
][2]=v
;
if(head
[r
]==-1) head
[r
]=right
[cnt
]=left
[cnt
]=cnt
;
else{
int tmp
=head
[r
];
right
[cnt
]=tmp
;
left
[cnt
]=left
[tmp
];
right
[left
[tmp
]]=cnt
;
left
[tmp
]=cnt
;
}
}
void del(int c
)
{
right
[left
[c
]]=right
[c
];
left
[right
[c
]]=left
[c
];
for(int i
=down
[c
];i
!=c
;i
=down
[i
]){
for(int j
=right
[i
];j
!=i
;j
=right
[j
]){
up
[down
[j
]]=up
[j
];
down
[up
[j
]]=down
[j
];
sz
[col
[j
]]--;
}
}
}
void res(int c
)
{
right
[left
[c
]]=left
[right
[c
]]=c
;
for(int i
=down
[c
];i
!=c
;i
=down
[i
]){
for(int j
=right
[i
];j
!=i
;j
=right
[j
]){
up
[down
[j
]]=down
[up
[j
]]=j
;
sz
[col
[j
]]++;
}
}
}
bool dance(int dep
)
{
if(dep
==81) return 1;
if(right
[0]==0) return 0;
int now
=right
[0];
for(int i
=now
;i
!=0;i
=right
[i
]){
if(sz
[i
]<sz
[now
]) now
=i
;
}
del(now
);
for(int i
=down
[now
];i
!=now
;i
=down
[i
]){
ans
[dep
]=i
;
for(int j
=right
[i
];j
!=i
;j
=right
[j
]) del(col
[j
]);
if(dance(dep
+1)) return 1;
for(int j
=left
[i
];j
!=i
;j
=left
[j
]) res(col
[j
]);
}
res(now
);
return 0;
}
}dlx
;
char s
[100];
void hhh(int v
,int x
,int y
,int &d
)
{
d
++;
int p1
=(x
-1)*9+y
;
int p2
=(x
-1)*9+v
+81;
int p3
=(y
-1)*9+v
+81*2;
int tmp
=((x
-1)/3)*3+(y
-1)/3+1;
int p4
=(tmp
-1)*9+v
+81*3;
dlx
.link(d
,p1
,x
,y
,v
);
dlx
.link(d
,p2
,x
,y
,v
);
dlx
.link(d
,p3
,x
,y
,v
);
dlx
.link(d
,p4
,x
,y
,v
);
}
int main()
{
while(~scanf("%s",s
)){
if(s
[0]=='e') break;
dlx
.init(81*9,81*4);
int r
=0;
for(int i
=0;i
<81;i
++){
int x
=i
/9+1;
int y
=i
%9+1;
if(s
[i
]=='.'){
for(int i
=1;i
<=9;i
++){
hhh(i
,x
,y
,r
);
}
}
else hhh(s
[i
]-'0',x
,y
,r
);
}
dlx
.dance(0);
int ans
[10][10];
for(int i
=0;i
<81;i
++){
int k
=dlx
.ans
[i
];
ans
[dlx
.get
[k
][0]][dlx
.get
[k
][1]]=dlx
.get
[k
][2];
}
for(int i
=1;i
<=9;i
++){
for(int j
=1;j
<=9;j
++){
printf("%d",ans
[i
][j
]);
}
}
printf("\n");
}
}
