DLX模板+小栗子

把别人的数独代码改了下就当自己模板了=。=，听说要启发函数效率才高=。=，下次再改改吧=。=

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define RN 1000
#define CN 500
#define NN 6000
class DLX{
private:
int U[NN],D[NN],L[NN],R[NN];
//每个节点的上下左右节点
int SUM[CN],COL[NN],ROW[NN];
//COL:节点的列位置 ROW:节点的行位置
//SUM:当前列有几个节点
int cd[CN],rl[RN],rr[RN],row,col,id;
//cd:此列最下节点 rr:此行最右节点 rl:此行最左节点
void remove(int c){
L[R[c]]=L[c];
R[L[c]]=R[c];
for(int i=D[c];i!=c;i=D[i]){
for(int j=R[i];j!=i;j=R[j]){
U[D[j]]=U[j];
D[U[j]]=D[j];
SUM[COL[j]]-=1;
}
}
}
void resume(int c){
for(int i=U[c];i!=c;i=U[i]){
for(int j=L[i];j!=i;j=L[j]){
U[D[j]]=D[U[j]]=j;
SUM[COL[j]]+=1;
}
}
L[R[c]]=R[L[c]]=c;
}
public:
int ANS[RN];
void ini(int c){
id=col=c+1;row=0;
memset(rl,-1,sizeof(rl));
memset(rr,-1,sizeof(rr));
int i;
for(i=0;i<col;i++){
if(i==0) L[i]=col-1;
else L[i]=i-1;
if(i==col-1) R[i]=0;
else R[i]=i+1;
SUM[i]=0;
cd[i]=i;
}
}
void del(int c){
L[R[c]]=L[c];
R[L[c]]=R[c];
}
void add(int r,int c[],int cn){
if(r>=row)row=r+1;
int i;
for(i=0;i<cn;i++){
U[id]=cd[c[i]];
D[cd[c[i]]]=id;
if(rr[r]!=-1){
L[id]=rr[r];
R[rr[r]]=id;
}else rl[r]=id;
rr[r]=id;
COL[id]=c[i];
ROW[id]=r;
SUM[c[i]]+=1;
cd[c[i]]=id;
id++;
}
}
int run(int k){
if(R[col-1]==col-1) return k;
int s=2000000000,c,i,j,r;
for(i=R[col-1];i!=col-1;i=R[i]){
if(SUM[i]<s) s=SUM[c=i];
}
remove(c);
for(r=D[c];r!=c;r=D[r]){
ANS[k]=ROW[r];
for(j=R[r];j!=r;j=R[j]){
remove(COL[j]);
}
int tmp=run(k+1);
if(tmp!=-1) return tmp;
for(j=L[r];j!=r;j=L[j]){
resume(COL[j]);
}
}
resume(c);
return -1;
}
void build_over(){
//上下对接
int i;
for(i=0;i<col;i++){
D[cd[i]]=i;
U[i]=cd[i];
}
//左右对接
for(i=0;i<row;i++){
if(~rr[i]){
L[rl[i]]=rr[i];
R[rr[i]]=rl[i];
}
}
}
};
/*
.xx...
x..x..
xx.xx.
....xx
*/
char mp[4][10]={".xx...","x..x..","xx.xx.","....xx"};
void use_dlx(){
int i,j,row=4,col=6,p[10],pn,res;
DLX dlx;
dlx.ini(col);
for(i=0;i<row;i++){
pn=0;
for(j=0;j<col;j++){
if(mp[i][j]=='x')p[pn++]=j;
}
dlx.add(i,p,pn);
}
dlx.build_over();
res=dlx.run(0);
for(i=0;i<res;i++)printf("%d ",dlx.ANS[i]);
printf("n");
}
int main(){
use_dlx();
return 0;
}

最后

以上就是沉静日记本为你收集整理的DLX模板+小栗子的全部内容，希望文章能够帮你解决DLX模板+小栗子所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。