第36届福州赛区1009 Squiggly Sudoku 解题报告
??? 裸的DLX，比一般的数独酷稍微复杂点的就是处理输入，先dfs一下，然后建十字链表。
??? 直接上代码了，跑得比较慢。
#include <cstdio>#include <cstring>using namespace std;const int INF = 0x7fffffff;const int NN = 350;const int MM = 750;int n,m; //列，行int cntc[NN];int L[NN*MM],R[NN*MM],U[NN*MM],D[NN*MM];int C[NN*MM]; //列的头链表int head;int mx[MM][NN];int O[MM],idx,idx2,O2[MM];int ans[10][10];int flags;//删除列及其相应的行void remove(int c){ int i,j; L[R[c]] = L[c]; R[L[c]] = R[c]; for(i = D[c]; i != c; i = D[i]) { for(j = R[i]; j != i; j = R[j]) { U[D[j]] = U[j]; D[U[j]] = D[j]; cntc[C[j]]--; } }}//恢复列及其相应的行void resume(int c){ int i,j; R[L[c]] = c; L[R[c]] = c; for(i = D[c]; i != c; i = D[i]) { for(j = R[i]; j != i; j = R[j]) { U[D[j]] = j; D[U[j]] = j; cntc[C[j]]++; } }}void dfs(){ int i,j,c; if(flags > 1) return; if(R[head] == head) { flags++; idx2 = idx; for(i = 0; i < idx; i++) O2[i] = O[i]; return; } int min = INF; for(i = R[head]; i != head; i = R[i]) { if(cntc[i] < min) { min = cntc[i]; c = i; } } remove(c); for(i = D[c]; i != c; i = D[i]) { //i是某点的序号，将该点所在行的行号保存 O[idx++] = (i-1)/n; for(j = R[i]; j != i; j = R[j]) remove(C[j]); dfs(); if(flags > 1) return; for(j = L[i]; j != i; j = L[j]) resume(C[j]); idx--; } resume(c);}void init(){ idx = idx2 = head = 0; flags = 0; for (int i = 0; i <= n; i++) { C[i] = i; D[i] = i; U[i] = i; cntc[i] = 0; R[i] = (i+1)%(n + 1); L[(i+1)%(n + 1)] = i; }}void insert(int r, int *mk){ int now, pre, first; for(int j = 0; j < 4; j++) { cntc[mk[j]]++; now = r*n+mk[j]; pre = U[mk[j]]; C[now] = mk[j]; D[pre] = now; U[now] = pre; D[now] = mk[j]; U[mk[j]] = now; } pre = first = -1; for (int i = 0; i < 4; i++) { now = r*n+mk[i]; if(pre == -1) first = now; else { R[pre] = now; L[now] = pre; } pre = now; } if(first != -1) { R[pre] = first; L[first] = pre; }}void print(){ int i,j; int x,y,k; for(i = 0; i < idx2; i++) { int r = O2[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; } if(flags == 0) printf("No solution\n"); else { if(flags > 1) printf("Multiple Solutions\n"); else { for(i = 1; i <= 9; i++) { for(j = 1; j <= 9; j++) printf("%d",ans[i][j]); printf("\n"); } } }}int d[4] = {128,64,32,16};int dir[4][2] = {{0,-1},{1,0},{0,1},{-1,0}};int mp[10][10];struct Point{ bool flag[4]; //左 下 右 上 int seq; int value;}p[10][10];bool change = 0;void floodfill(int i, int j, int seq){ if(p[i][j].seq > 0) return; p[i][j].seq = seq; for(int k = 0; k < 4; k++) { if(p[i][j].flag[k]) continue; int x = i + dir[k][0]; int y = j + dir[k][1]; if(x>=1&&x<=9&&y>=1&&y<=9&&p[x][y].seq==0) { change = 1; floodfill(x,y,seq); } }}int main(){ int i,j,k; int cases; scanf("%d",&cases); int tt = 0; while(cases--) { for(i = 1; i <= 9; i++) { for(j = 1; j <= 9; j++) { p[i][j].seq = 0; for(k = 0; k < 4; k++) p[i][j].flag[k] = 0; } } for(i = 1; i <= 9; i++) for(j = 1; j <= 9; j++) { scanf("%d",&mp[i][j]); for(k = 0; k < 4; k++) { if(mp[i][j] < 16) { p[i][j].value = mp[i][j]; break; } int t = mp[i][j]-d[k]; if(t >= 0) { p[i][j].flag[k] = 1; mp[i][j] = t; } } if(k == 4) p[i][j].value = mp[i][j]; } int seq = 1; for(i = 1; i <= 9; i++) { for(j = 1; j <= 9; j++) { change = 0; floodfill(i,j,seq); if(change) seq++; } } n = 324; m = 729; init(); for(i = 1; i <= 9; i++) { for(j = 1; j <= 9; j++) { int t = (i-1)*9 + j; if(p[i][j].value == 0) { for(k = 1; k <= 9; k++) { int tvec[5]; tvec[0] = t; tvec[1] = (81+(i-1)*9+k); tvec[2] = (162+(j-1)*9+k); tvec[3] = (243+(p[i][j].seq-1)*9+k); insert(9*(t-1)+k, tvec); } } else { int tvec[5]; k = p[i][j].value; tvec[0] = t; tvec[1] = (81+(i-1)*9+k); tvec[2] = (162+(j-1)*9+k); tvec[3] = (243+(p[i][j].seq-1)*9+k); insert(9*(t-1)+k, tvec); } } } printf("Case %d:\n",++tt); dfs(); print(); } return 0;}?