题意：有9*9的格子
每个格子 由五部分组成：上(16)、右(32)、下(64)、左(128)、和该格的数值(0~9)
若上下左右有分割格子的线 就加上相应的数， 该格的数值若为0，则是未知 1~9 则是已知
然后根据分割线 做数独(每行、每列、每宫都是1~9)
输出无解、多解或者一个解就输出那个解
这种数独与普通3*3的数独 的唯一区别就是 宫 的划分的方式不一样
16、32、64、128这几个数很特殊 分别是$2^4$、$2^5$、$2^6$、$2^7$
也就是相应的二位数，若第4位为1，则上面有分割线
若第5位为1，则右边有分割线
若第6位为1，则下面有分割线
若第7位为1，则左边有分割线
那么只要随便dfs一下确定在哪个宫里就好啦
然后把模板里 本来宫的位置是(i/3)*3+(j/3) 换成 dfs搜出来的宫的位置就好啦~
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
//const int N=2e5+5; const int N=; //3*3数独
const int MaxN=N*N*N+; // 一格能填9个数 9*9格
const int MaxM=N*N*+; // 9*9*4=(9+9+9)*9+9*9 (9+9+9)是9行 9列 9格 *9是9个数 9*9是81个格子
const int maxnode=MaxN*+MaxM+;
int g[MaxN];
int anss;
struct DLX
{
int n, m, size;
int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode];
int H[MaxN], S[MaxM]; // S: 各列节点数
int ansd, ans[MaxN];
void init(int _n, int _m)
{
n=_n;
m=_m;
for(int i=; i<=m; i++)
{
S[i]=; //每一列元素个数
U[i]=D[i]=i;//上下指针
L[i]=i-; //←
R[i]=i+; //→
}
R[m]=; //循环 最后一个指向第一个
L[]=m; //第一个往前指向最后一个
size=m; // 节点总数
for(int i=; i<=n; i++)
H[i]=-; //头指针
}
void Link(int r, int c)
{
S[Col[++size]=c]++;
Row[size]=r;
D[size]=D[c];
U[D[c]]=size;
U[size]=c;
D[c]=size;
if(H[r]<)
H[r]=L[size]=R[size]=size;
else
{
R[size]=R[H[r]];
L[R[H[r]]]=size;
L[size]=H[r];
R[H[r]]=size;
}
}
void remove(int c)
{
L[R[c]]=L[c];
R[L[c]]=R[c];
for(int i=D[c]; i!=c; i=D[i])
for(int j=R[i]; j!=i; j=R[j])
{
U[D[j]]=U[j];
D[U[j]]=D[j];
S[Col[j]]--;
}
}
void resume(int c)
{
for(int i=U[c]; i!=c; i=U[i])
for(int j=L[i]; j!=i; j=L[j])
S[Col[U[D[j]]=D[U[j]]=j]]++;
L[R[c]]=R[L[c]]=c;
}
void Dance(int d)
{
if(anss>)
return ;
if(R[]==)
{
for(int i=;i<d;i++)
g[(ans[i]-)/N]=(ans[i]-)%N+;
anss++;
}
int c=R[];
for(int i=R[]; i!=; i=R[i])
if(S[i]<S[c])
c=i;
remove(c);
for(int i=D[c]; i!=c; i=D[i])
{
ans[d]=Row[i];
for(int j=R[i]; j!=i; j=R[j])
remove(Col[j]);
Dance(d+);
for(int j=L[i]; j!=i; j=L[j])
resume(Col[j]);
}
resume(c);
}
} dlx;
int s[][];
int vis[][];
void dfs(int x,int y,int col)
{
if(x<||x>=||y<||y>=||vis[x][y]!=-)
return ;
if((s[x][y]&(<<))==)
{
vis[x][y]=col;
dfs(x,y-, col);
}
if((s[x][y]&(<<))==)
{
vis[x][y]=col;
dfs(x+,y, col);
}
if((s[x][y]&(<<))==)
{
vis[x][y]=col;
dfs(x,y+, col);
}
if((s[x][y]&(<<))==)
{
vis[x][y]=col;
dfs(x-,y, col);
}
} void palce(int &r, int &c1, int &c2, int &c3, int &c4, int i, int j, int k)
{
r=(i*N+j)*N+k; // 第几行
c1=i*N+j+; // 第几个格子
c2=N*N+i*N+k; // 第i行上的k
c3=N*N*+j*N+k; // 第j列上的k
c4=N*N*+(vis[i][j])*N+k; // 某宫中的k;
} int main()
{
int t, ca=;
scanf("%d", &t);
while(t--)
{
for(int i=;i<N;i++)
for(int j=;j<N;j++)
scanf("%d", &s[i][j]);
int num=;
memset(vis, -, sizeof(vis));
for(int i=;i<N;i++)
for(int j=;j<N;j++)
{
if(vis[i][j]==-)
dfs(i, j, num++);
if((s[i][j]-(<<))>=)
s[i][j]-=<<;
if((s[i][j]-(<<))>=)
s[i][j]-=<<;
if((s[i][j]-(<<))>=)
s[i][j]-=<<;
if((s[i][j]-(<<))>=)
s[i][j]-=<<;
}
dlx.init(N*N*N, *N*N);
for(int i=; i<N; i++)
for(int j=; j<N; j++)
for(int k=; k<=; k++)
if(s[i][j]== || s[i][j]==k)
{
int r, c1, c2, c3, c4;
palce(r, c1, c2, c3, c4, i, j, k);
dlx.Link(r, c1);
dlx.Link(r, c2);
dlx.Link(r, c3);
dlx.Link(r, c4);
}
anss=;
dlx.Dance();
printf("Case %d:\n", ca++);
if(anss==)
puts("No solution");
else if(anss>)
puts("Multiple Solutions");
else
{
for(int i=;i<N;i++)
{
for(int j=;j<N;j++)
printf("%d", g[i*N+j]);
puts("");
}
}
}
return ;
}
HDOJ 4069