AcWing - 169 - 数独2 - 舞蹈链

标签：define   ble   clr   freopen   print   over   clu   def   for   

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

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

#include 
#include 
#include 
using namespace std;
const int inf  = (-1u>>1); 
#define m 4
#define n 16
#define N n*n*n
#define M 4*n*n
char 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 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 R){
            if (size[p->c] 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 

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

AcWing - 169 - 数独2 - 舞蹈链

标签：define   ble   clr   freopen   print   over   clu   def   for   

原文地址：https://www.cnblogs.com/Inko/p/11663526.html