Dancing Links X
_Yoimiya_
·
·
题解
Dancing Links X 算法
一，算法概述
### 二， X 算法
所谓 X 算法...这就是一个深搜（~~太屑了~~）。
步骤
1.如果发现所有列都被标记则输出答案。
2.对当前矩阵删除当前行，并删去与当前行有公共元素（即同列有 1） 的所有行，递归下一层。
3.如果所有行返回无解即返回无解给上一层，并恢复行，回到第2步。
4.所有搜索无解则返回无解。
关于X算法，网上有许多生动的图解，这里已经说了步骤，不理解的可自行看代码或搜索其他题解，这里不再赘述（~~我太弱了不会讲~~）。
本题的 DFS 部分代码：
```cpp
inline bool dance(int deep){
if(!r[0]){
for(register int i(0);i<deep;++i)printf("%d ",ansk[i]);
return 1;//本题不要求多解，可以直接返回
}
int mini=r[0];//找到1最少的列（减少迭代次数）
for(register int i(r[0]);i!=0;i=r[i])if(s[i]<s[mini])mini=i;
removed(mini);
for(int i(d[mini]);i!=mini;i=d[i]){
ansk[deep]=row[i];
for(int j=r[i];j!=i;j=r[j]) removed(col[j]);
if(dance(deep+1))return 1;//递归下一层
for(int j=l[i];j!=i;j=l[j]) resumed(col[j]);
}
resumed(mini);
return 0;//返回无解
}
```
### 三，十字链表（四向循环链表）
- <1> 循环链表
循环链表是一种链式存储结构，链表中最后一个结点的指针域指向头结点，整个链表形成一个环。
- <2> 四向循环链表 ( Dancing Links )
又称十字链表，相当于四个方向（上下左右）都有指针，构成四个循环链表。这种特殊的结构可以使其快速地进行移除和回复操作(正好对应X算法需要的操作)，四个方向的指针之间的变换犹如舞蹈一般美丽又不失巧妙，因此被称为“舞蹈链”。
十字链表初始化
```cpp
void init(int m)//一般不用传n，构建矩阵只用m个头元素
{
cnt=m+1;//开始时有m个结点（0结点和各列头结点）
memset(h,-1,sizeof h);//将头结点赋为-1，表示没有
for(int i=0;i<=m;i++){
u[i]=d[i]=i;
l[i]=i-1;r[i]=i+1;//十字链表基本原理
}
```
对于插入新节点（注意，这里比较难懂，建议不理解的画一下图，模拟一下指针的变化）
```cpp
inline void link(int R,int C){//在R行C列插入一个1
s[C]++;//s数组表示每列的结点数
col[cnt]=C;row[cnt]=R;//记录这个点的行列信息
u[cnt]=C;d[cnt]=d[C];u[d[C]]=cnt;d[C]=cnt;//链表插入
if(h[R]==-1) l[cnt]=cnt,h[R]=cnt,r[cnt]=cnt;//如果没有头，那它就是头
else{
r[cnt]=h[R];l[cnt]=l[h[R]];r[l[h[R]]]=cnt;l[h[R]]=cnt;
}
++cnt;return ;//下一个点的编号
}
```
移除与恢复C列上有点的行，我觉得这里最能体现“指针的舞蹈”的巧妙。
对于移除行操作（不用释放内存，因为这只是暂时的）
```cpp
inline void removed(int C){
r[l[C]]=r[C];l[r[C]]=l[C];//它左边的右边指向它的右边，它右边的左边指向它的左边（我觉得很巧妙）
for(register int i(d[C]);i!=C;i=d[i]){
for(register int j(r[i]);j!=i;j=r[j]){
u[d[j]]=u[j];//同理
d[u[j]]=d[j];
--s[col[j]];
}
}return ;
}
```
对于恢复操作（注意恢复要和移除方向相反）
```cpp
inline void resumed(int C){
r[l[C]]=C;l[r[C]]=C;
for(register int i(u[C]);i!=C;i=u[i]){//相反方向
for(register int j(l[i]);j!=i;j=l[j]){
u[d[j]]=j;d[u[j]]=j;++s[col[j]];
}
}return ;
}
```
### 四，整体代码
本题代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx=250510;
inline int Read(){
int x=0;char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
int n,m,cnt;
int l[mx],r[mx],u[mx],d[mx],col[mx],row[mx],h[mx],s[mx],ansk[mx];
void init(int m){
cnt=m+1;
memset(h,-1,sizeof h);
for(register int i(0);i<=m;++i){
u[i]=d[i]=i;
l[i]=i-1;r[i]=i+1;
}
l[0]=m;r[m]=0;
}
inline void link(int R,int C){
s[C]++;col[cnt]=C;row[cnt]=R;
u[cnt]=C;d[cnt]=d[C];u[d[C]]=cnt;d[C]=cnt;
if(h[R]==-1) l[cnt]=cnt,h[R]=cnt,r[cnt]=cnt;
else{
r[cnt]=h[R];l[cnt]=l[h[R]];r[l[h[R]]]=cnt;l[h[R]]=cnt;
}
++cnt;return ;
}
inline void removed(int C){
r[l[C]]=r[C];l[r[C]]=l[C];
for(register int i(d[C]);i!=C;i=d[i]){
for(register int j(r[i]);j!=i;j=r[j]){
u[d[j]]=u[j];
d[u[j]]=d[j];
--s[col[j]];
}
}return ;
}
inline void resumed(int C){
r[l[C]]=C;l[r[C]]=C;
for(register int i(u[C]);i!=C;i=u[i]){
for(register int j(l[i]);j!=i;j=l[j]){
u[d[j]]=j;d[u[j]]=j;++s[col[j]];
}
}return ;
}
inline bool dance(int deep){
if(!r[0]){
for(register int i(0);i<deep;++i)printf("%d ",ansk[i]);
return 1;
}
int mini=r[0];
for(register int i(r[0]);i!=0;i=r[i])if(s[i]<s[mini])mini=i;
removed(mini);
for(int i(d[mini]);i!=mini;i=d[i]){
ansk[deep]=row[i];
for(int j=r[i];j!=i;j=r[j]) removed(col[j]);
if(dance(deep+1))return 1;
for(int j=l[i];j!=i;j=l[j]) resumed(col[j]);
}
resumed(mini);
return 0;
}
signed main(){
n=Read(),m=Read();
init(m);
for(register int i(1);i<=n;++i)
for(register int j(1);j<=m;++j)
if(Read())link(i,j);
if(!dance(0))printf("No Solution!");
return 0;
}
```
好题推荐：
| Dominoes | http://acm.hdu.edu.cn/showproblem.php?pid=2518 |
| :----------: | :----------: |
| N 皇后 | https://www.spoj.com/problems/NQUEEN/ |
| Lamp | http://acm.hdu.edu.cn/showproblem.php?pid=2828 |
|靶形数独|https://www.luogu.com.cn/problem/P1074|
感谢阅读！