dancing link模板

 #include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std; const int n=,m=;
bool mx[][];//数独转化过来的01矩阵
int map[][],cnt[],head,cur,ans;
int sqr[][]={{,,,,,,,,,}, //九宫格的编号
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,}}; int w[][]={{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,}}; struct point
{
int row,lc,rc,up,down,col;//元素的上下左右,行号和列标
}node[*]; inline int id(int x,int y)
{
return (x-)*+y;//格子(x,y)的编号
} void init(int c)//初始化列标元素
{
for (int i=;i<=c;i++)
{
node[i].lc=i-;
node[i].rc=i+;
node[i].up=node[i].down=node[i].col=i;
}
node[].lc=c;
node[c].rc=;
} void build_link()//把01矩阵中的 1 用dancing link 连接
{
cur=m;
for (int i=;i<=n;i++)
{
int start,pre;
start=pre=cur+;
for (int j=;j<=m;j++)
if (mx[i][j])
{
cur++;
cnt[j]++;
node[cur].row=i; node[cur].lc=pre;
node[cur].rc=start;
node[pre].rc=cur;
node[start].lc=cur; node[cur].col=j;
node[cur].up=node[j].up;
node[cur].down=j;
node[node[j].up].down=cur;
node[j].up=cur;
pre=cur;
}
}
} inline void cover(int c)//删除冲突元素
{
for (int i=node[c].up;i!=c;i=node[i].up)
for (int j=node[i].rc;j!=i;j=node[j].rc)
{
node[node[j].up].down=node[j].down;
node[node[j].down].up=node[j].up;
cnt[node[j].col]--;
}
node[node[c].lc].rc=node[c].rc;
node[node[c].rc].lc=node[c].lc;
} inline void uncover(int c)//恢复冲突元素
{
for (int i=node[c].up;i!=c;i=node[i].up)
for (int j=node[i].rc;j!=i;j=node[j].rc)
{
node[node[j].up].down=j;
node[node[j].down].up=j;
cnt[node[j].col]++;
}
node[node[c].lc].rc=c;
node[node[c].rc].lc=c;
} void read_data()//把数独转化成01矩阵
{
for (int i=;i<=;i++)
for (int j=;j<=;j++)
{
scanf("%d",&map[i][j]);
int c=id(i,j),t,k;
if (map[i][j])//数独中本来有数,直接加入
{
k=map[i][j];
t=(c-)*+k;
mx[t][c]=true;
mx[t][+*(i-)+k]=true;
mx[t][+*(j-)+k]=true;
mx[t][+(sqr[i][j]-)*+k]=true;
}
else
{
for (k=;k<=;k++) //数独中本来没数,那么加入1-9的情况
{
t=(c-)*+k;
mx[t][c]=true;
mx[t][+*(i-)+k]=true;
mx[t][+*(j-)+k]=true;
mx[t][+(sqr[i][j]-)*+k]=true;
}
}
}
} bool dfs(int step,int score)
{
if (node[head].rc==head) //已经全部覆盖
{
ans=max(score,ans);
return true;
} int i,j,c,t=,x,y,num,flag=;
for (i=node[head].rc;i!=head;i=node[i].rc) //启发式,每次处理元素最少的列
if (cnt[i]<t)
{
t=cnt[i];
c=i;
}
if (t==)
return false; cover(c);//覆盖当前列 for (i=node[c].down;i!=c;i=node[i].down)
{
for (j=node[i].lc;j!=i;j=node[j].lc)//删除冲突的行
cover(node[j].col);
num=(node[i].row-)/+;
x=(num-)/+;
y=num-*(x-);
flag|=dfs(step+,score+w[x][y]*(node[i].row-(num-)*));
for (j=node[i].rc;j!=i;j=node[j].rc)//恢复删除冲突的行
uncover(node[j].col);
} uncover(c);//恢复当前列
return flag;
} void solve()
{
init(m);
build_link();
int flag=;
if (!dfs(,))
printf("-1\n");
else printf("%d\n",ans);
} int main()
{
read_data();
solve();
return ;
}
上一篇:Java多线程初学者指南(9):为什么要进行数据同步


下一篇:Python语言基础-语法特点、保留字与标识符、变量、基本数据类型、运算符、基本输入输出、Python2.X与Python3.X区别