颠覆了自己对于搜索的认知……
Part1. 引入
有一个 $n\times m$ 的方格图,其中有一些格子上有棋子。你可以选择一些行(整行),使得在选择的部分中,每一列上都恰好有 $1$ 个棋子。输出任意一种解决方案。
$n,m\leq50$,时限:1秒
来源:
对于这种问题,没有特别有效的解决方法,只能暴力搜索(需要回溯)。但是由于 $n$ 较大,我们没有办法暴力判断选择哪些行,也没有特别好的剪枝方法。
但是我们注意到问题只要求任意一种解决方案,只要我们搜索的 更新可选方案(当我们选择一行后,一些之前可能选择的行,现在不能选择,就需要删掉)、回溯 的速度比较快,就能够相对较快地解决这个问题。
其实这个问题就是:精确覆盖问题,解决方法就是 Dancing Links。
Part2. 十字循环链表
既然是 “跳舞链”,这里的链就是“十字循环链表”。这种链表的元素有 $4$ 个指针 L[],R[],U[],D[]
,分别表示左、右、上、下的元素;并且这样的元素是“循环的”。
Part2/1. 建表
链表是建立在方格图上的(既然是循环链表,最左、最右 和 最上、最下 是相邻的,且是双向的):
记方格图有 $n$ 行、$m$ 列。
整个链表有一个表头 head=0
,然后我们再用 $m$ 个元素分别表示一列。head
与这 $m$ 个元素排成一行,左右相连(第 $m$ 个元素的右边是 head
)。记表示第 $i$ 列的元素是 C[i]
。
对于第 $i$ 列,最上方和最下方的格点与 C[i]
上下相连;同列上下相连,同行的格点左右相连。
这样就构造出了一个十字循环链表。
不难发现如果我们把 Part1 中的“棋子”看作方格图中的格点(也就是上图蓝色的格子),也可以建出一个十字循环矩阵。
Part2/2. 删除元素
有两种删除的方式——左右删除和上下删除。左右删除即 “删除前元素 x
的左右元素在删除后与 x
不相连” ,上下删除则是 “删除前元素 x
的上下元素在删除后与 x
不相连”。
由于是双向链表,我们可以方便地找到一个元素在方格图中上下左右的元素。那么我们可以这样实现删除:
1 2 3 4 5
|
L[R[x]]=L[x];R[L[x]]=R[x];
U[D[x]]=U[x];D[U[x]]=D[x];
|
注意到这里只是修改了 x
的上下左右元素的指针,而对于 x
本身的指针并没有修改,这样保证了链表能够在删除元素后“撤销删除”。
Part2/3. 撤销删除元素
既然是撤销,就只能按删除的顺序倒序撤销。
比如我们上一步删除了 x
,现在我们要撤销这一次删除。利用删除时并没有修改的 x
的指针,我们还能够找到 x
在删除之前的上下左右的元素。
和删除相似,撤销也包括左右撤销和上下撤销。
1 2 3 4 5
|
L[R[x]]=R[L[x]]=x;
U[D[x]]=D[U[x]]=x;
|
Part3. Dancing Links
下面进入正题,但是上面不是废话。
首先 Dancing Links ,我理解的话,就是一个链表优化剪枝、回溯的搜索……
我们改变一下思路 —— 不考虑当前要选择哪一行,而是考虑当前要满足哪一列上恰好有一个棋子被选。
假设我们选择的列是第 Vc
列,我们选择的方式是从 0
(表头)开始枚举同行的元素(因为是循环的,只需要向右就可以了)。然后再启发式搜索一下,也就是选择元素最少的列(这就意味着必须要维护一列的个数)。
1 2 3 4 5 6
| int mn=INF,Vc; for(int i=Er[0];i!=0;i=Er[i]) if(Sc[i]<mn && i<=n*m){ mn=Sc[i]; Vc=i; }
|
选择了 Vc
后,我们就要删除 Vc
以确保之后不会再选择到 Vc
。
然后为了满足第 Vc
列上有一个棋子,就要枚举选择第 i
行,满足第 i
行第 Vc
列上有棋子,这个可以通过链表方便的找到(因为链表上的元素除了代表某一列的元素 C[]
以及表头,其他的元素都代表的是一个棋子)。
选择了第 i
行后,如果第 i
行第 j
列有棋子,那么第 j
列也会同时被满足,那么第 j
列也要被删掉。然后再DFS。结束后回溯要倒序撤销删除操作。整个DFS结束时也要撤销删除第 Vc
列。
1 2 3 4 5 6 7 8 9
| Remove(Vc); for(int i=D[Vc];i!=Vc;i=D[i]){ for(int j=R[i];i!=j;j=R[j]) Remove(col[j]); DFS(); for(int j=L[i];i!=j;j=L[j]) Resume(col[j]); } Resume(Vc);
|
Part3/1. Remove(int Vc)
如果我们要删除第 Vc
列,就表示“第 Vc
列上已经有一个被选中的棋子”,那么我们就不能再在选择 Vc
时选择到该元素 ,也不能再选择第 Vc
列的一个棋子。
根据我们选择 Vc
的方式——从表头开始向右枚举元素。只要我们从表头开始向右枚举不到第 Vc
列就可以了!也就是删除元素 C[Vc]
(代表第 Vc
列的元素)—— L[R[C[Vc]]]=L[C[Vc]];R[L[C[Vc]]]=C[Vc]
。
但是不止删除 C[Vc]
,为了防止之后选择到第 Vc
列的棋子:如果第 i
行第 j
列有棋子,那么第 i
行就不能选,否则第 j
列就有多个棋子了。那么我们要删除第 i
行的所有元素,也可以通过链表迅速找到这些元素。
1 2 3 4 5 6 7 8 9 10 11
| void Remove(int Vc){ L[R[C[Vc]]]=L[C[Vc]];R[L[C[Vc]]]=C[Vc]; for(int i=D[Vc];i!=Vc;i=D[i]) for(int j=R[i];j!=i;j=R[j]){ U[D[j]]=U[j];D[U[j]]=D[j]; Sc[col[j]]--; } }
|
注意到这里并不会更改删除的元素本身的信息,目的是方便接下来的“撤销删除”操作。
Part3/2. Resume(int Vc)
在回溯的时候会用到“撤销删除”,但是只能按删除顺序的倒序撤销。
其实倒过来就可以了……
1 2 3 4 5 6 7 8
| void Resume(int Vc){ for(int i=U[Vc];i!=Vc;i=U[i]) for(int j=L[i];j!=i;j=L[j]){ U[D[j]]=D[U[j]]=j; Sc[col[j]]++; } L[R[C[Vc]]]=R[L[C[Vc]]]=C[Vc]; }
|
Part3/3. DLX
终于到整个的 跳舞链 部分了
之前都把该写的部分都写了,现在组合起来就可以了—— 不过有一个不一样的地方,为了方便,我们并没有定义 C[i]
是代表第 i
列的元素,而是直接让元素 i
是代表第 i
列的元素(也可以理解为 C[i]=i
)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
| struct DANCINGLINKS{ int El[LM],Er[LM],Eu[LM],Ed[LM],Ec[LM],Sc[LM]; int Vcol,ncnt; void Build(){ } void Remove(int Vc){ El[Er[Vc]]=El[Vc];Er[El[Vc]]=Er[Vc]; for(int i=Ed[Vc];i!=Vc;i=Ed[i]){ for(int j=Er[i];j!=i;j=Er[j]){ Ed[Eu[j]]=Ed[j];Eu[Ed[j]]=Eu[j]; Sc[Ec[j]]--; } } } void Resume(int Vc){ for(int i=Eu[Vc];i!=Vc;i=Eu[i]){ for(int j=El[i];j!=i;j=El[j]){ Eu[Ed[j]]=j;Ed[Eu[j]]=j; Sc[Ec[j]]++; } } El[Er[Vc]]=Vc;Er[El[Vc]]=Vc; } void DFS(int Vk){ if(R[0]==0){ ans++; return; } int mn=(1<<29),Vc=-1; for(int i=Er[0];i!=0;i=Er[i]) if(Sc[i]<mn && i<=n*m){ mn=Sc[i]; Vc=i; } if(Vc==-1) return; Remove(Vc); for(int i=Ed[Vc];i!=Vc;i=Ed[i]){ for(int j=Er[i];j!=i;j=Er[j]) Remove(Ec[j]); DFS(Vk+1); for(int j=El[i];j!=i;j=El[j]) Resume(Ec[j]); } Resume(Vc); } }
|
Part4. 模板题 & 其他题
首先就是一开始的 引入 了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
| #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
const int N=100,LN=N*N+N+10;
int n,m; int Cc[N+3][N+3];
struct DANCINGLINKS{ int El[LN],Er[LN],Eu[LN],Ed[LN],Ec[LN],Sc[LN]; int Vh,ncnt; void Build(){ Vh=0; for(int i=0;i<=m;i++){ if(i==0) El[i]=m,Er[i]=1; else if(i==m) El[i]=m-1,Er[i]=0; else El[i]=i-1,Er[i]=i+1; Eu[i]=Ed[i]=i; Sc[i]=0;Ec[i]=i; } ncnt=m; for(int i=1;i<=n;i++){ int Vbg=ncnt+1,Ved=Vbg; for(int j=1;j<=m;j++){ if(!Cc[i][j]) continue; int Vu=Eu[j],Vd=j,it=++ncnt; Eu[it]=Vu;Ed[it]=Vd; Eu[Vd]=it;Ed[Vu]=it; El[it]=Ved;Er[it]=Vbg; Er[El[it]]=it;El[Er[it]]=it; Ved=it; Sc[j]++;Ec[it]=j; } } } void Remove(int Vc){ El[Er[Vc]]=El[Vc];Er[El[Vc]]=Er[Vc]; for(int i=Ed[Vc];i!=Vc;i=Ed[i]){ for(int j=Er[i];j!=i;j=Er[j]){ Ed[Eu[j]]=Ed[j];Eu[Ed[j]]=Eu[j]; Sc[Ec[j]]--; } } } void Resume(int Vc){ for(int i=Eu[Vc];i!=Vc;i=Eu[i]){ for(int j=El[i];j!=i;j=El[j]){ Eu[Ed[j]]=j;Ed[Eu[j]]=j; Sc[Ec[j]]++; } } El[Er[Vc]]=Vc;Er[El[Vc]]=Vc; } bool DFS(int Vk){ if(Er[Vh]==Vh) return true; int mn=(1<<29),Vc; for(int i=Er[Vh];i!=Vh;i=Er[i]) if(Sc[i]<mn){ mn=Sc[i]; Vc=i; } Remove(Vc); for(int i=Ed[Vc];i!=Vc;i=Ed[i]){ for(int j=Er[i];j!=i;j=Er[j]) Remove(Ec[j]); if(DFS(Vk+1)) return true; for(int j=El[i];j!=i;j=El[j]) Resume(Ec[j]); } Resume(Vc); return false; } }DLX;
int main(){ int cas;scanf("%d",&cas); while(cas--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&Cc[i][j]); DLX.Build(); printf("%s\n",DLX.DFS(1)? "Yes":"No"); } return 0; }
|
Part4/1. n皇后问题
每行、每列都要有恰好 1 个皇后……也就是精确覆盖问题。但是也有一点不一样,就是对于斜线的限制——每条斜线上最多有一个皇后。
那么我们把棋盘的行、列、斜线都作为精确覆盖问题的“列”,每个位置作为“行”。表示斜线的“列”不一定要覆盖完,于是就不能通过判断链表是否为空来判断是否找到答案了,我们发现我们每次会确定一个皇后的位置,如果已经放下了 n 个皇后,就找到答案了。(即搜索深度=n+1)
链接:
Part4/2. 数独
每行、每列、$3\times3$ 的方格内恰好要有一个 $1$ ~ $9$,这就是精确覆盖问题的限制条件。然后就成为一道板子了。
The End
Thanks for reading!
Email: lucky_glass@foxmail.com ,欢迎提问~