$$\color{Purple}{kuangbin题解目录}$$
描述
请你将一个 $16 \\times 16$ 的数独填写完整,使得每行、每列、每个 $4 \\times 4$ 十六宫格内字母 $A \\sim P$ 均恰好出现一次。
保证每个输入只有唯一解决方案。
输入格式
输入包含多组测试用例。
每组测试用例包括 $16$ 行,每行一组字符串,共 $16$ 个字符串。
第 $i$ 个字符串表示数独的第 $i$ 行。
字符串包含字符可能为字母 $A \\sim P$ 或 -
(表示等待填充)。
测试用例之间用单个空行分隔,输入至文件结尾处终止。
输出格式
对于每个测试用例,均要求保持与输入相同的格式,将填充完成后的数独输出。
每个测试用例输出结束后,输出一个空行。
输入样例:
--A----C-----O-I
-J--A-B-P-CGF-H-
--D--F-I-E----P-
-G-EL-H----M-J--
----E----C--G---
-I--K-GA-B---E-J
D-GP--J-F----A--
-E---C-B--DP--O-
E--F-M--D--L-K-A
-C--------O-I-L-
H-P-C--F-A--B---
---G-OD---J----H
K---J----H-A-P-L
--B--P--E--K--A-
-H--B--K--FI-C--
--F---C--D--H-N-
输出样例:
FPAHMJECNLBDKOGI
OJMIANBDPKCGFLHE
LNDKGFOIJEAHMBPC
BGCELKHPOFIMAJDN
MFHBELPOACKJGNID
CILNKDGAHBMOPEFJ
DOGPIHJMFNLECAKB
JEKAFCNBGIDPLHOM
EBOFPMIJDGHLNKCA
NCJDHBAEKMOFIGLP
HMPLCGKFIAENBDJO
AKIGNODLBPJCEFMH
KDEMJIFNCHGAOPBL
GLBCDPMHEONKJIAF
PHNOBALKMJFIDCEG
IAFJOECGLDPBHMNK
思路
- 构建的$01$矩阵,以
每个位置可填16个数
(即有$16\times 16 \times 16=4096$行,可适当开大一点)作为横坐标,以当前位置是否填数,当前行是否有该数,当前列是否有该数,当前方格是否有该数
(即有$4\times 16\times 16 =1024$列,可适当开大点)作为纵坐标;- 设当前位置的坐标是$(x,y)$(下标从$0$开始),对应方格一维化为$\frac{x}{4}\times 4+\frac{y}{4}$,填的数是$num$(此处数范围是$1\le num \le 16$,最后转为字符即可).
每个位置可填16个数
转化为对应的行是$\color{Red}{(x\times 16 + y)\times 16 + num}$
当前位置是否填数
,列可表示为$\color{Red}{x\times 16+y+1}$,共$256$个.
当前行是否有该数
,列可表示为$\color{Red}{16\times 16 + x\times 16 +num}$,共$256$个.
当前列是否有该数
,列可表示为$\color{Red}{2\times 16\times 16 + y\times 16 +num}$,共$256$个.
当前方格是否有该数
,列可表示为$\color{Red}{3\times 16\times 16 + (\frac{x}{4}\times 4+ \frac{y}{4})\times 16 +num}$,共$256$个.
代码
// Problem: 数独2
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/171/
// Memory Limit: 64 MB
// Time Limit: 2000 ms
// Date: 2023-01-16 16:03:42
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 4100
#define MAXM 1100
#define MAXP (MAXN*MAXM)
using namespace std;
typedef long long ll;
string s[20];
struct Dancing_Links_Node{
int Up;
int Down;
int Left;
int Right;
int row;//行数
int col;//列数
};
int cnt=0;//记录结点个数
Dancing_Links_Node node[MAXP];
int f_row[MAXN];//记录每行的第一个元素
int c_cnt[MAXM];//每列元素个数
int res[260];//保存最终结果
int temp[260];
void Init_Node(int num)//初始化head和列元素,将其上下左右指针指好,行数和列数可不用初始化
{
for(int i=0;i<=num;i++)
{
node[i].Left=i-1;//左-1
node[i].Right=i+1;//右+1
node[i].Up=i;//上下指向自己
node[i].Down=i;
c_cnt[i]=0;//列个数清空
}
node[0].Left=num;//让head的左边指向最后一个的列元素
node[num].Right=0;//让最后一个的列元素的右边指向head
cnt=num;//更新结点个数
memset(f_row,-1,sizeof(f_row));
}
void Insert_Node(int x,int y){//插入新节点(链式前向星的构图方式)
//更新具体值
node[++cnt].row=x;//更新行数
node[cnt].col=y;//更新列数
//先处理该结点的所在列链上的情况
node[cnt].Down=node[y].Down;//更新当前元素的指向下面
node[node[y].Down].Up=cnt;//之前的最后一个元素指向最后
node[cnt].Up=y;
node[y].Down=cnt;
//然后处理该结点的所在行链上的情况
if(f_row[x]<0)//表示该结点是其所在行的第一个元素
{
node[cnt].Left=cnt;//自己指向自己
node[cnt].Right=cnt;//自己指向自己
f_row[x]=cnt;//更新当前行的第一个元素
}
else//表示该结点不是其所在行的第一个元素
{
node[cnt].Right=node[f_row[x]].Right;
node[node[f_row[x]].Right].Left=cnt;
node[cnt].Left=f_row[x];
node[f_row[x]].Right=cnt;
}
c_cnt[y]++;//当前列元素+1
}
void Remove_Link(int y)//删除列元素所在的列链 及 其中元素所对应行
{
for(int i=node[y].Down;i!=y;i=node[i].Down)//枚举列链中的元素
{
for(int j=node[i].Right;j!=i;j=node[j].Right)//枚举列链中元素所对应行链中元素并删除
{
node[node[j].Down].Up=node[j].Up;
node[node[j].Up].Down=node[j].Down;
//当前元素删除后,该元素的下面元素指向上面的是当前元素的上面元素
//当前元素删除后,该元素的上面元素指向下面的是当前元素的下面元素
c_cnt[node[j].col]--;//当前列的元素-1
}
}
//删除列链(仅需删除列元素即可删除整个列链)
node[node[y].Left].Right=node[y].Right;
node[node[y].Right].Left=node[y].Left;
//当前列元素的左面元素指向右边面的是当前元素的右面元素
//当前列元素的右面元素指向左边面的是当前元素的左面元素
}
void Resume_Link(int y)//恢复列元素所在列链 及 其中元素所对应行
{
//恢复列链(仅需恢复列元素即可恢复整个列链)
node[node[y].Left].Right=y;
node[node[y].Right].Left=y;
for(int i=node[y].Up;i!=y;i=node[i].Up)//枚举列链中的元素
for(int j=node[i].Left;j!=i;j=node[j].Left)//枚举列链中元素所对应行链中元素并恢复
{
node[node[j].Down].Up=j;
node[node[j].Up].Down=j;
//当前元素的上面元素指向下面的是当前元素
//当前元素的下面元素指向上面的是当前元素
c_cnt[node[j].col]++;//当前列的元素+1
}
}
int dance(int depth)//depth表示答案的个数(所搜的层数)
{
if(node[0].Right==0)//如果head.right=head,说明有解,输出答案
{
//1-16存的是(0,0)的情况
//res[i]存的是满足的行,求的对应的位置为(res[i]-1)/16
//最终的结果是(res[i]-1)%16+1
for(int i=0;i<depth;i++)
temp[(res[i]-1)/16]=(res[i]-1)%16+1;
for(int i=0;i<=15;i++)
{
for(int j=0;j<=15;j++)
cout << char(temp[i*16+j]+'A'-1);
cout << endl;
}
cout << endl;//若在ZOJ提交,记得注释该行
return 1;
}
int y=node[0].Right;//取列元素y=head.right
for(int i=node[0].Right;i!=0;i=node[i].Right)//剪枝(减少搜索树的分叉)
if(c_cnt[i]<c_cnt[y])
y=i;
Remove_Link(y);//删除列链
for(int i=node[y].Down;i!=y;i=node[i].Down)
{
res[depth]=node[i].row;
for(int j=node[i].Right;j!=i;j=node[j].Right)//删除选择行链元素所在列链
Remove_Link(node[j].col);
if(dance(depth+1)==1)
return 1;
for(int j=node[i].Left;j!=i;j=node[j].Left)//恢复选择行链元素所在列链
Resume_Link(node[j].col);
}
Resume_Link(y);//恢复列链
return 0;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int flag=0;
while(cin >> s[0])
{
/* ZOJ需要这样写(不然格式错误)
if(flag==1)
cout << endl;
flag=1;
*/
for(int i=1;i<=15;i++)
cin >> s[i];
Init_Node(16*16*4);
for(int x=0;x<=15;x++)
for(int y=0;y<=15;y++)
for(int num=1;num<=16;num++)
if(s[x][y]=='-'||s[x][y]==num+'A'-1)//此处当该位置未填时把所有情况放入链中,反之把当前数放入链中
{
int temp_row=(x*16+y)*16+num;
int temp_col_1=x*16+y+1;
int temp_col_2=16*16+x*16+num;
int temp_col_3=2*16*16+y*16+num;
int temp_col_4=3*16*16+(x/4*4+y/4)*16+num;
Insert_Node(temp_row,temp_col_1);
Insert_Node(temp_row,temp_col_2);
Insert_Node(temp_row,temp_col_3);
Insert_Node(temp_row,temp_col_4);
}
dance(0);
}
return 0;
}