题目链接：点我啊╭(╯^╰)╮
题目大意：
给你一个锯齿数独的图，每个凹凸形状的宫的上下左右边界以及格子里的数字都给出相应的计算规则，要你求这个数独的唯一解，或者输出 0 0 0 解或多解
解题思路：
数独模板题，关键在于宫的变换，我们回想之前处理数独的宫的方法，首先要对每个数字所处在的宫进行编号，所以用BFS对每个宫进行搜索编号，然后直接将编好号的图建立模型
这里因为会存在多解，所以要对DLX精准覆盖里的dfs进行修改，在第一次找到答案的时候一定要把答案记录下来，不然在后续的搜索过程中会将答案覆盖掉
代码思路：
BFS对图编号后进行DLX精准覆盖
核心：对数独的宫进行合理化处理
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int flag;
struct DancingLink{const static int N = 500010;const static int M = 1010;int n, s, ansd, ansd_real; //列数 节点总数 int S[M], A[M], H[M], A_real[M]; // S[]该列节点总数 A[]答案 H[]行首指针 int L[N], R[N], U[N], D[N]; // L[],R[],U[],D[] 上下左右 int X[N], C[N]; // X[] C[] 行列编号 void init(int n){ // 初始化 this->n = n;for(int i=0; i<=n; i++)U[i]=i, D[i]=i, L[i]=i-1, R[i]=i+1;R[n]=0, L[0]=n; s=n+1;memset(S, 0, sizeof(S));memset(H, -1, sizeof(H));}void DelCol(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[C[j]];}void ResCol(int c){ // 恢复列 for(int i=U[c]; i!=c; i=U[i])for(int j=L[i]; j!=i; j=L[j])++S[C[j]], U[D[j]]=j, D[U[j]]=j;L[R[c]]=c, R[L[c]]=c;}void AddNode(int r,int c){ // 添加节点 ++S[c], C[++s]=c, X[s]=r;D[s]=D[c], U[D[c]]=s, U[s]=c, D[c]=s;if(H[r]<0) H[r]=L[s]=R[s]=s; // 行首节点else R[s]=R[H[r]], L[R[H[r]]]=s, L[s]=H[r], R[H[r]]=s;}void dfs(int d){ // 深度，深搜遍历 if(flag>1) return;if(!R[0]) {flag++; if(flag>1) return;ansd_real = d;for(int i=0; i<d; i++) A_real[i] = A[i];return;}int c=R[0];for(int i=R[0]; i; i=R[i]) if(S[i]<S[c]) c=i;DelCol(c);for(int i=D[c]; i!=c; i=D[i]) {A[d]=X[i];for(int j=R[i]; j!=i; j=R[j]) DelCol(C[j]);dfs(d+1);for(int j=L[i]; j!=i; j=L[j]) ResCol(C[j]);}ResCol(c);}
} dlx;int nid, ans[10][10], mp[10][10];
int wall[10][10][5], id[10][10];
int encode(int a, int b, int c) {return a*81+(b-1)*9+c;
}
int decode() {int x,y,k;for(int i=0; i<dlx.ansd_real; i++) {int r = dlx.A_real[i];k = r%9;if(k==0) k = 9;int num = (r - k)/9 + 1;y = num%9;if(y == 0) y = 9;x = (num-y)/9 + 1;ans[x][y] = k;}
}int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
queue <pair<int, int>> Q;void BFS(int n, int m){while(!Q.empty()) Q.pop();Q.push(make_pair(n, m));id[n][m] = nid;while(!Q.empty()){int q1 = Q.front().first;int q2 = Q.front().second;Q.pop();for(int i=0; i<4; i++){int x = q1 + dx[i];int y = q2 + dy[i];if(wall[q1][q2][i] || id[x][y]) continue;id[x][y] = nid;Q.push(make_pair(x,y));} }nid++;
}int main() {int t, cas = 1;scanf("%d", &t);while(t--) {for(int i=1; i<=9; i++)for(int j=1; j<=9; j++)scanf("%d", &mp[i][j]);dlx.init(9*9*4);memset(wall,0,sizeof(wall));for(int i=1; i<=9; i++)for(int j=1; j<=9; j++) {if(mp[i][j]>=128) //左墙mp[i][j]-=128, wall[i][j][0]=1;if(mp[i][j]>=64) //下墙mp[i][j]-=64, wall[i][j][3]=1;if(mp[i][j]>=32) //右墙mp[i][j]-=32, wall[i][j][1]=1;if(mp[i][j]>=16) //上墙mp[i][j]-=16, wall[i][j][2]=1;}nid = 1;memset(id,0,sizeof(id));for(int i=1; i<=9; i++)for(int j=1; j<=9; j++)if(!id[i][j]) BFS(i, j);for(int i=1; i<=9; i++)for(int j=1; j<=9; j++)for(int k=1; k<=9; k++)if(!mp[i][j] || mp[i][j]==k) {int t = encode(0,i,j);int r = encode(0,t,k);dlx.AddNode(r,t);dlx.AddNode(r,encode(1,i,k));dlx.AddNode(r,encode(2,j,k));dlx.AddNode(r,encode(3,id[i][j],k));}flag = dlx.ansd_real = 0;dlx.dfs(0);decode();printf("Case %d:\n", cas++);if(dlx.ansd_real == 0)printf("No solution\n");else if(flag>1)printf("Multiple Solutions\n");else {for(int i=1; i<=9; i++){for(int j=1; j<=9; j++)printf("%d", ans[i][j]);puts("");} }}
}