20210914下午
搜索？狗都不用。
| T1 | T2 | T3 | T4 | T5 |
|---|---|---|---|---|
| 预测 | 100 | 100 | 100 | 60 |
| 一测 | 100 | 100 | 100 |
T1：
简单搜索。。。按顺序搜就行
T2：
提示把剪枝都讲了，实在是太良心了。
T3：
不是，凭什么 n = 8000 n=8000 n=8000能搜出来啊。。。我本来想写 10 10 10个 h a s h hash hash暴力了。。。
爆搜能搜出来。。。而且题面是 N o s o l u t i o n ! No\ \ solution! No solution!，答案是 N o S o l u t i o n ! No\ \ Solution! No Solution!。
T4：
经典搜索加模拟，其实蛮简单的，只有消去和坠落两个操作要注意。
一些剪枝：
1.如果当前同一颜色只有 1 1 1块或 2 2 2块就结束游戏，无解。
2.只有右边为空时才往左边移，否则一定往右移更优。
3.如果是相同色块就无需交换。
贴个代码吧。
struct game{ //游戏状态
int s[10][10]; //块色
int col[15]; //每种颜色个数，用于剪枝1
bool cl[10][10]; //清除标记
void Read() //读入
{
int tmp;
for(int i=1;i<=5;i++) for(int j=1;scanf("%d",&tmp)&&tmp;j++) s[i][j]=tmp;
return;
}
bool empty() //是否消完
{
for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) if(s[i][j]) return false;
return true;
}
bool clear() //消块
{
bool res=false;
for(int i=1;i<=5;i++)
{
for(int j=1,k,c;j<=7;j++)
{
c=s[i][j];if(!c) continue;
for(k=i;k<=5&&s[k+1][j]==c;k++); //向右拓展
if(k-i+1>=3) {res=true;for(int l=i;l<=k;l++) cl[l][j]=true;}
for(k=j;k<=7&&s[i][k+1]==c;k++); //向上拓展
if(k-j+1>=3) {res=true;for(int l=j;l<=k;l++) cl[i][l]=true;}
}
}
for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) if(cl[i][j]) s[i][j]=0,cl[i][j]=false; //消去
return res;
}
void fall() //坠落
{
for(int j=2;j<=7;j++) for(int i=1;i<=5;i++) for(int k=j;k>1&&s[i][k]&&!s[i][k-1];k--) swap(s[i][k],s[i][k-1]); //下面为空就一直掉
return;
}
bool over() //剪枝1
{
memset(col,0,sizeof(col));
for(int i=1;i<=5;i++) for(int j=1;j<=7;j++) col[s[i][j]]++;
for(int i=1;i<=10;i++) if(col[i]>=1&&col[i]<=2) return true;
return false;
}
}st;
void Dfs(int x,game now) //搜索
{
if(flag) return;
now.fall(); //可能上次移向空处
while(now.clear()) now.fall(); //能消就一直消
if(now.over()) return;
if(x==n+1)
{
if(now.empty()) print(),flag=true;
return;
}
game nxt;nxt=now;
for(int i=1;i<=5;i++)
{
for(int j=1;j<=7;j++)
{
if(!now.s[i][j]) continue;
if(in(i+1,j)&&now.s[i+1][j]!=now.s[i][j]) //剪枝3
{
swap(nxt.s[i+1][j],nxt.s[i][j]);
ans[x].x=i;ans[x].y=j;ans[x].f=1;
Dfs(x+1,nxt);
if(flag) return;
swap(nxt.s[i+1][j],nxt.s[i][j]);
}
if(!now.s[i-1][j]) //剪枝2
{
if(!in(i-1,j)||now.s[i-1][j]==now.s[i][j]) continue; //剪枝3
swap(nxt.s[i-1][j],nxt.s[i][j]);
ans[x].x=i;ans[x].y=j;ans[x].f=-1;
Dfs(x+1,nxt);
if(flag) return;
swap(nxt.s[i-1][j],nxt.s[i][j]);
}
}
}
return;
}
思路很清晰的模拟。
T5：
《关于我用搜索怎么剪都剪不过就去学 D a n c i n g L i n k s X Dancing\ \ Links\ \ X Dancing Links X然后 40 m s 40ms 40msA了数独这件事》
搜索我就不多说了，就算我加了按最小选择排序也过不了，可能是我的问题。
下面我来隆重介绍 D a n c i n g L i n k s X Dancing\ \ Links\ \ X Dancing Links X算法。
D L X DLX DLX是由 X X X算法通过十字链表优化而来，用于解决精准覆盖问题。
什么是精准覆盖问题？
可以理解为给出 n n n个集合和一个全集，要求选出一些集合使他们不重复地构成全集，也就是 S 1 ∪ S 2 ∪ S 3 ⋯ = S S_1\cup S_2 \cup S_3 \dots =S S1∪S2∪S3⋯=S且 S 1 ∩ S 2 ∩ S 3 ⋯ = ∅ S_1 \cap S_2 \cap S_3 \dots=\varnothing S1∩S2∩S3⋯=∅。
举个例子，现在有集合
S = { 114 , 233 , 514 , 7 , 1926 , 817 , 666 } S=\{114,233,514,7,1926,817,666\} S={114,233,514,7,1926,817,666}
S 1 = { 114 , 514 , 7 } S_1=\{114,514,7\} S1={114,514,7}
S 2 = { 114 , 1926 , 817 , 666 } S_2=\{114,1926,817,666\} S2={114,1926,817,666}
S 3 = { 514 , 817 , 666 } S_3=\{514,817,666\} S3={514,817,666}
S 4 = { 114 } S_4=\{114\} S4={114}
S 5 = { 114 , 233 , 7 , 1926 } S_5=\{114,233,7,1926\} S5={114,233,7,1926}
S 6 = { 514 , 7 , 1926 , 66 } S_6=\{514,7,1926,66\} S6={514,7,1926,66}
S 7 = { 233 , 514 , 7 } S_7=\{233,514,7\} S7={233,514,7}
S 8 = { 233 , 817 } S_8=\{233,817\} S8={233,817}
可以一眼看出这个问题的精准覆盖为 S 2 S_2 S2和 S 7 S_7 S7或 S 3 S_3 S3和 S 5 S_5 S5或 S 4 S_4 S4， S 6 S_6 S6和 S 8 S_8 S8。
那么 X X X算法是如何解决这个问题的呢？
首先，我们把这些关系转化为矩阵
S 114 233 514 7 1926 817 666 S 1 1 0 1 1 0 0 0 S 2 1 0 0 0 1 1 1 S 3 0 0 1 0 0 1 1 S 4 1 0 0 0 0 0 0 S 5 1 1 0 1 1 0 0 S 6 0 0 1 1 1 0 1 S 7 0 1 1 1 0 0 0 S 8 0 1 0 0 0 1 0 \begin{matrix} S&114&233&514&7&1926&817&666 \\ S_1&1&0&1&1&0&0&0 \\ S_2&1&0&0&0&1&1&1 \\ S_3&0&0&1&0&0&1&1 \\ S_4&1&0&0&0&0&0&0 \\ S_5&1&1&0&1&1&0&0 \\ S_6&0&0&1&1&1&0&1 \\ S_7&0&1&1&1&0&0&0 \\ S_8&0&1&0&0&0&1&0 \end{matrix} SS1S2S3S4S5S6S7S81141101100023300001011514101001107100011101926010011008170110000166601100100
然后，我们先假设选择了 S 1 S_1 S1，显然我们就不能选那些在 S 1 S_1 S1上有数的集合，那么我们就去删除这些行和列
得到
S 233 1926 817 66 S 8 1 0 1 0 \begin{matrix} S&233&1926&817&66 \\ S_8 &1&0&1&0 \end{matrix} SS82331192608171660
接着我们选择 S 8 S_8 S8并进行同样的操作。
S 1926 66 \begin{matrix} S&1926&66 \end{matrix} S192666
发现集合被删完了， S S S却还有剩，说明选 S 1 S_1 S1无法得到答案，于是回溯恢复被删除的行和列并不再考虑 S 1 S_1 S1
之后选择 S 2 S_2 S2
得到
S 233 514 7 S 7 1 1 1 \begin{matrix} S&233&514&7 \\ S_7&1&1&1 \end{matrix} SS72331514171
选择 S 7 S_7 S7， S S S被删完，说明找到一组答案，若不是多组答案可以直接退出程序了。
若要找多组答案，则继续回溯，选择 S 3 S_3 S3
得到
S 114 233 7 1926 S 4 1 0 0 0 S 5 1 1 1 1 \begin{matrix} S&114&233&7&1926 \\ S_4&1&0&0&0 \\ S_5&1&1&1&1 \end{matrix} SS4S51141123301701192601
若选择 S 4 S_4 S4，那么有
S 233 7 1926 \begin{matrix} S&233&7&1926 \end{matrix} S23371926
无解，回溯选择 S 5 S_5 S5，发现消完，找到另一组解。
回溯选择 S 4 S_4 S4
得到
S 233 514 7 1926 817 666 S 6 0 1 1 1 0 1 S 7 1 1 1 0 0 0 S 8 1 0 0 0 1 0 \begin{matrix} S&233&514&7&1926&817&666 \\ S_6&0&1&1&1&0&1 \\ S_7&1&1&1&0&0&0 \\ S_8&1&0&0&0&1&0 \end{matrix} SS6S7S823301151411071101926100817001666100
选择 S 6 S_6 S6，得到
S 233 817 S 8 1 1 \begin{matrix} S&233&817 \\ S_8&1&1 \end{matrix} SS823318171
删去后再次得到一组解。
后面就不模拟了（做图做麻了，不过大概意思应该都知道了，这就是 X X X算法的大致流程。
可以发现此算法需要大量的删除行列和恢复的操作，所以如果朴素实现，其指数级复杂度取决于矩阵中 1 1 1的个数，大概只能接受 n , m ≤ 100 n,m\le 100 n,m≤100的矩阵。
所以我们的十字链表优化就来啦， D L X DLX DLX横空出世。（其实并没有，它也不是啥省选内容。
下面偷一下DLX 详细讲解的图来简单介绍一下十字链表（我真的做不来啊淦。
十字链表拥有四个指针左 l l l右 r r r上 u u u下 d d d，以这些指针来存储一个矩阵。
完整版大概是张这样的。
当然，除了上面的几个数组，还有 f i r s t i first_i firsti表示每一行的行首，每一列的列首则是由 0 0 0节点连接出的虚拟节点。
另外需要一个 s i z i siz_i sizi记录每列的节点个数。
所以大概需要这几个数组
int n,m,tot,first[N],siz[N]; //tot表示节点编号
int l[N],r[N],u[N],d[N];
int row[N],col[N]; //表示该节点的行列
接下来是几个操作
1.建表
构建一个 R × C R\times C R×C的空矩阵，只需将每一列的虚节点建出来就行。
void build(int R,int C)
{
n=R;m=C;
for(int i=0;i<=C;i++) l[i]=i-1,r[i]=i+1,u[i]=d[i]=i;
l[0]=C;r[C]=0;tot=C; //每一行列都是环状链表，新节点从C+1开始
memset(first,0,sizeof(first));
memset(siz,0,sizeof(siz));
return;
}
另外建议使用以下形式访问环状链表
2.插入
在 ( R , C ) (R,C) (R,C)处插入一个点，相当于我们在矩阵内插入一个 1 1 1。
定义该节点为 t o t tot tot，在列上，直接进行操作。
将 t o t tot tot上方改为 C C C， t o t tot tot下方改为原来 C C C下方的节点，原来 C C C下方节点的上方改为 t o t tot tot， C C C下方节点改为 t o t tot tot。
即
对行，进行分类。
若该行还没有 f i r s t first first节点，将 f i r s t first first直接改为 t o t tot tot。
若该行有 f i r s t first first节点了，将 t o t tot tot左边改为 f i r s t R first_R firstR，右边改为原来 f i r s t R first_R firstR的右边， f i r s t R first_R firstR右边节点的左边改为 t o t tot tot， f i r s t R first_R firstR的右边改为 t o t tot tot
即
if(!first[R]) first[R]=l[tot]=r[tot]=tot;
else l[tot]=first[R],r[tot]=r[first[R]],l[r[first[R]]]=tot,r[first[R]]=tot;
都是很好理解的链表操作，完整如下
void insert(int R,int C)
{
row[++tot]=R;col[tot]=C;siz[C]++;
u[tot]=C,d[tot]=d[C],u[d[C]]=tot,d[C]=tot;
if(!first[R]) first[R]=l[tot]=r[tot]=tot;
else l[tot]=first[R],r[tot]=r[first[R]],l[r[first[R]]]=tot,r[first[R]]=tot;
return;
}
3.移除
对于移除列 C C C的操作，我们需要移除这一列与向下访问到的每一行。
移除这一列很简单，将 C C C左右节点的左右指针修改即可。
接着向下访问每个节点，再横向访问哪一行，将节点上下节点修改以删去那一行。
完成修改操作。
void remove(int C)
{
l[r[C]]=l[C];r[l[C]]=r[C];
IT(i,d,C) IT(j,r,i) u[d[j]]=u[j],d[u[j]]=d[j],siz[col[j]]--;
return;
}
4.恢复
其实就是把移除操作反过来弄一遍。
void recover(int C)
{
IT(i,d,C) IT(j,r,i) u[d[j]]=d[u[j]]=j,siz[col[j]]++;
l[r[C]]=r[l[C]]=C;
return;
}
以上就是我们需要的所有操作，然后与 X X X算法结合就是 D L X DLX DLX算法了。
bool dance(int dep,int *s)
{
int C=r[0]; //若0无右节点，说明矩阵为空，算法结束
if(!C) {···;return true;} //处理答案
IT(i,r,0) if(siz[i]<siz[C]) C=i; //找一个结点最少的列以减少搜索树
remove(C);
IT(i,d,C)
{
s[dep]=row[i];
IT(j,r,i) remove(col[j]);
if(dance(dep+1,s)) return true; //镜像操作，若多组数据就不用return
IT(j,r,i) recover(col[j]);
s[dep]=0;
}
recover(C);
return false;
}
（叫 D a n c i n g L i n k s X Dancing\ \ Links\ \ X Dancing Links X是因为搜索过程在各行中跳）
可以通过【模板】舞蹈链（DLX）了。
D L X DLX DLX的复杂度为 O ( c n ) O(c^n) O(cn)，其中 n n n为矩阵中 1 1 1的个数，而 c c c是一个十分接近于 1 1 1的常数，所以一般可以通过大部分题目。
不过该算法还有一个难点，将题目要求抽象成集合与矩阵。
我们回到数独这道题本身上来。
在 i i i行 j j j列 w w w宫 ( i , j , w ) (i,j,w) (i,j,w)填一个数 k k k，因为 w w w可以由 i , j i,j i,j确定，所以我们只需要 i × j × k i\times j\times k i×j×k即 9 × 9 × 9 = 729 9\times 9\times 9=729 9×9×9=729行（个集合）。
而这个操作又会引起哪些扰动呢。
会使 ( i , j ) (i,j) (i,j)位置被占
会使 i i i行 k k k这个数无法使用。
会使 j j j列 k k k这个数无法使用。
会使 w w w宫 k k k这个数无法使用。
每种都需要 81 81 81列来存储，所以共 81 × 4 = 324 81\times 4=324 81×4=324列（集合大小）。
所以，我们成功将数独问题转化为一个 729 × 324 729\times 324 729×324的精确覆盖问题。
代码和模板的区别在于插入结点。
#include<bits/stdc++.h>
#define IT(i,A,x) for(int i=A[x];i!=x;i=A[i]) //好用
using namespace std;
const int N=1e5+5; //数组要开矩阵大小
int a,s[N],ans[105][105];
class Orthogonal_List{ //十字链表
public:
int n,m,tot,first[N],siz[N];
int l[N],r[N],u[N],d[N];
int col[N],row[N];
void build(int R,int C)
{
n=R;m=C;
for(int i=0;i<=C;i++) l[i]=i-1,r[i]=i+1,u[i]=d[i]=i;
l[0]=C;r[C]=0;tot=C;
memset(first,0,sizeof(first));
memset(siz,0,sizeof(siz));
return;
}
void insert(int R,int C)
{
row[++tot]=R;col[tot]=C;siz[C]++;
u[tot]=C,d[tot]=d[C],u[d[C]]=tot,d[C]=tot;
if(!first[R]) first[R]=l[tot]=r[tot]=tot;
else l[tot]=first[R],r[tot]=r[first[R]],l[r[first[R]]]=tot,r[first[R]]=tot;
return;
}
void remove(int C)
{
l[r[C]]=l[C];r[l[C]]=r[C];
IT(i,d,C) IT(j,r,i) u[d[j]]=u[j],d[u[j]]=d[j],siz[col[j]]--;
return;
}
void recover(int C)
{
IT(i,d,C) IT(j,r,i) u[d[j]]=d[u[j]]=j,siz[col[j]]++;
l[r[C]]=r[l[C]]=C;
return;
}
bool dance(int dep)
{
int C=r[0];
if(!C) {for(int i=1,x,y,z;i<dep;i++) {x=((s[i]-1)/9)/9+1;y=((s[i]-1)/9)%9+1;z=(s[i]-1)%9+1;ans[x][y]=z;};return true;}
IT(i,r,0) if(siz[i]<siz[C]) C=i;
remove(C);
IT(i,d,C)
{
s[dep]=row[i];
IT(j,l,i) remove(col[j]); //这里用两个IT(j,r,i)就会错，其他都行，玄学。。。
if(dance(dep+1)) return true;
IT(j,r,i) recover(col[j]);
s[dep]=0;
}
recover(C);
return false;
}
}lis;
char ch[100];
int main()
{
while(scanf("%s",ch+1)&&ch[1]!='e')
{
lis.build(729,324); //建图
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
a=ch[(i-1)*9+j]=='.'?0:ch[(i-1)*9+j]-'0';
for(int k=1,l;k<=9;k++)
{
if(a-k&&a) continue; //其实就是有值就只填a，为空就每个都填
l=((i-1)*9+(j-1))*9+k; //行
lis.insert(l,(i-1)*9+j); //i行j列
lis.insert(l,81+(i-1)*9+k); //i行k数
lis.insert(l,162+(j-1)*9+k); //j列k数
lis.insert(l,243+(((i-1)/3)*3+(j-1)/3)*9+k); //w宫k数
}
}
}
lis.dance(1); //你你你你要跳舞吗
for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) putchar(ans[i][j]+'0');putchar('\n');
}
return 0;
}
完结撒花。
总结：搜索是有极限的，所以我直接摆烂啦。