[ZSOI 简单数谜]DFS+调整搜索顺序

【题目】

Description

　 很多人都曾经听说过数独，但你是否听说过数谜（Karuro）呢？实际上，数谜是数独的更大（且更难）的兄弟问题，而且在日本也是非常受欢迎的。
数谜问题和填字游戏类似，不过它要填的不是文字而是数字。数谜游戏的目标是用1-9填满所有空格，且这些数字相加的和满足相应的要求（或者称为“提 示”），且在同一栏（“栏”是指一些水平或者竖直的连续的空格，用于提示的格子不算空格）不能填重复的数字。当所有格子按要求被填满后，这个数谜就看作被 解决了。图1和图2是一个可能的数谜游戏示例。
当然，直接求解数谜问题的话会比较困难。所以现在我们需要解决的是一个更简单的数谜问题。简单数谜的形状是一个(n+1）行乘(m+1)列的矩 形。而简单数谜也只有两种要求，就是行要求和列要求，且分别处于第一行和第一列，其他格子则是空格，而左上角是忽略不计的。coolzzz同学爱好简单数 谜，他已经给一些简单数谜填好了其中的一些空格。现在，他想寻求你的帮助，来帮他完成这些简单数谜。如图3所示，2和9是coolzzz同学已经填好的空 格，图4则是一个基于图3 的一个可能的解答。

Input

　　输入包含多组测试数据。第一行包含一个正整数T，表示测试数据数目。每组数据第一行是n(n<10)和m(m<10)，表示数谜的形状的 大小。接下来一行有n个整数，是相应的行要求；然后一行是m个整数，是相应的列要求。接下来的n行每行有m个小于10的非负整数，0表示该空格还没有被填 数字，其他表示coolzzz同学已经填好的数字。输入数据保证未填数字的空格不会超过16个。

Output

　　对于每组测试数据，输出若干行。如果基于coolzzz已填的结果，该数谜只有一个解，则输出该解；如果不止一个解，则输出一行“Not unique.”；如果没有解，则输出一行“No answer.”。

Sample Input

3
3 3
6 6 6
6 6 6
0 0 0
0 3 0
0 0 0
2 3
10 17
5 16 6
2 0 0
0 9 0
2 2
3 5
4 4
0 0
0 0

Sample Output

Not unique.
2 7 1
3 9 5
No answer.

【算法分析】
类似数独的搜索题，然后就是设一个简单的估价函数，按它的值排下序，然后再用位运算优化一下就可以很快出解。
另外传说的DLX应该会有更好的表现。。。
【CODE】
#include #include #include const int N=10;
const double rate=0.02;
struct LL{int x,y;double w;}L[N*N];
int n,m,tot,ans;
int limitx[N],limity[N],canx[N],cany[N],donex[N],doney[N];
int a[N][N],lg[2000],ansl[N][N];
bool flag;

void input(){
memset(donex,0,sizeof(donex));
memset(doney,0,sizeof(doney));
flag=true;
tot=0;
scanf("%d%d",&m,&n);
for (int i=0;i for (int i=0;i for (int i=0;i for (int i=0;i for (int i=0;i for (int j=0;j scanf("%d",&a[i][j]);
if (a[i][j]){
limitx[i]-=a[i][j];
limity[j]-=a[i][j];
if (canx[i]&(1< if (cany[j]&(1< if (limitx[i]<0) flag=false;
if (limity[j]<0) flag=false;
canx[i]^=1< cany[j]^=1< donex[i]++;
doney[j]++;
}else{
tot++;
L[tot].x=i;
L[tot].y=j;
}
}
}

int cmp(const void *x,const void *y){
if (((LL*)x)->w>((LL*)y)->w) return 1;
if (((LL*)x)->w<((LL*)y)->w) return -1;
if (((LL*)x)->w==((LL*)y)->w) return 0;
}

void init(){
for (int i=1;i<=tot;i++)
L[i].w=donex[L[i].x]+doney[L[i].y]+rate*(limitx[L[i].x]+limity[L[i].y]);
qsort(&L[1],tot,sizeof(LL),cmp);
}

inline int sqr(int x){return x*(x+1)/2;}

void dfs(int dep){
LL &Node=L[dep];
if (dep==tot+1){
ans++;
if (ans>1) return;
memcpy(ansl,a,sizeof(a));
}
int state=canx[Node.x]&cany[Node.y],p;
while (state){
p=state&-state;
if (limitx[Node.x]-lg[p] if (limity[Node.y]-lg[p] a[Node.x][Node.y]=lg[p];
limitx[Node.x]-=lg[p];
limity[Node.y]-=lg[p];
donex[Node.x]++;
doney[Node.y]++;
canx[Node.x]-=p;
cany[Node.y]-=p;
if (!(donex[Node.x]==n && limitx[Node.x]!=0))
if (!(doney[Node.y]==m && limity[Node.y]!=0))
dfs(dep+1);
if (ans>1) return;
a[Node.x][Node.y]=0;
limitx[Node.x]+=lg[p];
limity[Node.y]+=lg[p];
donex[Node.x]–;
doney[Node.y]–;
canx[Node.x]+=p;
cany[Node.y]+=p;
state-=p;
}
}

void solve(){
if (ans>1) printf("Not unique.n");
if (ans==0) printf("No answer.n");
if (ans==1)
for (int i=0;i for (int j=0;j printf("%d",ansl[i][j]);
if (j==n-1) printf("n");
else printf(" ");
}
}

int main(){
lg[1]=0;
for (int i=2;i<=1024;i++){
lg[i]=lg[i-1];
if (i==1< }
for (int i=1;i<=1024;i++) lg[i]++;
freopen("kakuro.in","r",stdin);
freopen("kakuro.out","w",stdout);
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
input();
if (!flag){
printf("No answer.n");
continue;
}
ans=0;
init();
dfs(1);
solve();
}
}