https://www.acwing.com/problem/content/description/171/

舞蹈链还是比较好，抄了一个看起来可以改的模板？

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int inf = (-1u>>1); #define m 4#define n 16#define N n*n*n#define M 4*n*nchar s[20][20];struct node{ int r,c; node *L,*R,*U,*D;};node DD[N*4+5], row[N+5], col[M+5], head;int cnt, size[M+5], ans[n+5][n+5];inline void init(int r, int c){ cnt = 0; head.L = head.R = head.U = head.D = &head; for (int i = 0; i < c; i++){ col[i].c = i; col[i].r = r; col[i].L = &head; col[i].R = head.R; col[i].L->R = col[i].R->L = &col[i]; col[i].U = col[i].D = &col[i]; size[i] = 0; } for (int i = r - 1; i >= 0; i--){ row[i].r = i; row[i].c = c; row[i].D = &head; row[i].U = head.U; row[i].U->D = row[i].D->U = &row[i]; row[i].L = row[i].R = &row[i]; }}inline void delLR(node *p){ p->L->R = p->R; p->R->L = p->L;}inline void delUD(node *p){ p->U->D = p->D; p->D->U = p->U;} inline void recLR(node *p){ p->L->R = p->R->L = p;}inline void recUD(node *p){ p->U->D = p->D->U = p;} inline void add(int r, int c){ node *p = &DD[cnt++]; p->c = c; p->r = r; p->U = &col[c]; p->D = col[c].D; p->U->D = p->D->U = p; p->R = &row[r]; p->L = row[r].L; p->L->R = p->R->L = p; size[c]++;} void cover(int c){ if (c == M) return; delLR(&col[c]); node *p, *q; for (p = col[c].D; p != (&col[c]); p = p->D){ for (q = p->L ; q != p; q = q->L){ if (q->c == M) continue; delUD(q); size[q->c]--; } }} void resume(int c){ if (c == M) return ; node *p, *q; for (p = col[c].U; p != (&col[c]); p = p->U){ for (q = p->R; q != p; q = q->R){ if (q->c == M) continue; recUD(q); size[q->c]++; } } recLR(&col[c]);}bool DLX(int k){ node *p; if (head.L == (&head)){ for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++) printf("%c", ans[i][j] + 'A'); puts(""); } puts(""); return true; } int MIN = inf, c = 1; for (p = head.R; p != (&head); p = p->R){ if (size[p->c] < MIN){ MIN = size[p->c]; c = p->c; } } cover(c); for (p = col[c].D; p != (&col[c]); p = p->D){ node *q; for (q = p->L; q != p; q = q->L){ cover(q->c); } int rr = p->r; ans[rr / (n*n)][(rr/n) % n] = rr % n; if (DLX(k + 1)) return true; for (q = p->R; q != p; q = q->R) resume(q->c); } resume(c); return false;} void insert(int i, int j, int k){ int r = (i * n + j) * n + k - 1; add(r, i * n + k - 1); add(r, n * n + j * n + k - 1); add(r, 2 * n * n + (i / m * m + j / m ) * n + k - 1); add(r, 3 * n * n + i * n + j);} void Sudoku(){ int k; for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ if (s[i][j] != '-') insert(i, j, s[i][j] - 'A' + 1); else { for (int k = 1; k <= n; k++) insert(i, j, k); } } } if (!DLX(0)) puts("NO Solution!");} int main(){ //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); while (scanf("%s", s[0]) != EOF){ for (int i = 1; i < n; i++)scanf("%s", s[i]); init(N, M); Sudoku(); } // getchar(); return 0;} 

作者：zhagoodwell
链接：https://www.acwing.com/solution/acwing/content/4110/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。