靶形数独代码
钱逸凡
2018-07-06 13:27:25
DLX不懂的[点这里](https://www.luogu.org/blog/ONE-PIECE/qian-tan-dlx)
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mx 100100
long long sum=0;
long long max(long long a,long long b){
return a>b?a:b;
}
inline int Read(){
int x=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
int volue[9][9]={
{6,6,6,6,6,6,6,6,6},
{6,7,7,7,7,7,7,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,9,10,9,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,7,7,7,7,7,7,6},
{6,6,6,6,6,6,6,6,6}
};
struct DLX{
int n,m,cnt;//矩阵的长，宽，点的数量
int l[mx],r[mx],u[mx],d[mx],row[mx],col[mx];//每个点的左，右，上下，行，列信息
int h[mx];//每行的头结点
int s[mx];//每列的结点数
int ans,ansk[mx];//选了ans行，分别为ansk[]
void init(int _n,int _m){
n=_n,m=_m;
int i;
for(i=0;i<=m;i++){
r[i]=i+1;l[i]=i-1;u[i]=d[i]=i;
}
r[m]=0;//m右边是0
l[0]=m;//0左边是m
memset(h,-1,sizeof(h));
memset(s,0,sizeof(s));
cnt=m+1;//开始时有m个结点（0结点和各列头结点）
}//初始化，生成每列的头
void link(int R,int C){
s[C]++;
row[cnt]=R;
col[cnt]=C;
u[cnt]=C;
d[cnt]=d[C];
u[d[C]]=cnt;
d[C]=cnt;
if(h[R]<0)h[R]=r[cnt]=l[cnt]=cnt;//该行没有别的点,把第一个加入的点作为该行的行头结点
else{
r[cnt]=h[R];
l[cnt]=l[h[R]];
r[l[h[R]]]=cnt;
l[h[R]]=cnt;
}
cnt++;
}//在r行c列插入点
void remove(int c){
r[l[c]]=r[c],l[r[c]]=l[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];
s[col[j]]--;
}
}
}//删除c列和c列上有点的行
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]]=j;
d[u[j]]=j;
s[col[j]]++;
}
}
r[l[c]]=c;
l[r[c]]=c;
}//恢复c列和c列上有点的行
void dance(int deep){
if(r[0]==0){
ans=deep;
long long ss=0;
int x,y,v;
for(int i=0;i<ans;i++){
x=(ansk[i]-1)/9/9;
y=(ansk[i]-1)/9%9;
v=(ansk[i]-1)%9;
ss+=volue[x][y]*(v+1);//把选的集合转换成对应的点
}
sum=max(sum,ss);
return;
}//找到答案就计算最优
int c=r[0];
for(int i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;//找到点最少的列
remove(c);
for(int i=d[c];i!=c;i=d[i]){
ansk[deep]=row[i];
for(int j=r[i];j!=i;j=r[j]) remove(col[j]);
dance(deep+1);
for(int j=l[i];j!=i;j=l[j]) resume(col[j]);
}
resume(c);
return ;
}
}dlx;
int main(){
dlx.init(729,324);
//729:
//9^4种情况对应9^4行;
//324:
//对应数独的规则:每个格子，每行，每列，每个九宫只能填1~9各一次
//对于第m列：
//若m在[1,81]表示在(m/9，m%9)填数
//若m在[81*1,81*2]在第1+（m-81）/9行填1+（m-81）%9
//若m在[81*2,81*3]在第1+（m-81*2）/9列填1+（m-81*2）%9
//若m在[81*3,81*4]在第1+（m-81*3）/9格填1+（m-81*3）%9
int x;
int o;
for(int i=0;i<=8;i++){
for(int j=0;j<=8;j++){
x=Read();
for(int k=1;k<=9;k++){
if(x!=k&&x!=0)continue;//已经填好的点就不用考虑了
o=i*9*9+j*9+k;
dlx.link(o,i*9+j+1);
dlx.link(o,i*9+81+k);
dlx.link(o,j*9+81*2+k);
dlx.link(o,81*3+(i/3*3+j/3)*9+k);//把点转换成对应的集合
}
}
}
dlx.dance(0);
if(sum!=0)printf("%lld",sum);
else printf("-1");
return 0;
}
```