[DLX 数独 模板题] HDU 1426 Sudoku Killer

关于DLX解数独戳这里 好评

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline bool read(char &x){
  for (x=getchar();!((x>='0' && x<='9') || x=='?');x=getchar()) if (x==EOF) return 0; return 1;
}

const int N=1005;
const int M=2000005;

int ncnt;
int L[M],R[M],U[M],D[M],row[M],col[M];
int size[N];
int ans[N],pnt;

inline void del(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],size[col[j]]--;
}
inline void rec(int c){
  L[R[c]]=R[L[c]]=c;
  for (int i=U[c];i!=c;i=U[i])
    for (int j=L[i];j!=i;j=L[j])
      U[D[j]]=D[U[j]]=j,size[col[j]]++;
}


inline bool dance(){
  if (R[0]==0)
    return 1;
  int c=R[0];
  for (int i=R[0];i;i=R[i]) if (size[i]<size[c]) c=i;
  del(c);
  for (int i=D[c];i!=c;i=D[i]){
    ans[++pnt]=row[i];
    for (int j=R[i];j!=i;j=R[j]) del(col[j]);
    if (dance()) return 1;
    for (int j=L[i];j!=i;j=L[j]) rec(col[j]);
    ans[pnt--]=0;
  }
  rec(c);
  return 0;
}

int newr;
int _x[N],_y[N],_k[N];

inline void addline(int a,int b,int c,int d){
  for (int i=1;i<=4;i++) L[ncnt+i]=ncnt+i-1,R[ncnt+i]=ncnt+i+1;
  L[ncnt+1]=ncnt+4; R[ncnt+4]=ncnt+1;
  U[++ncnt]=U[a]; D[ncnt]=a; U[D[ncnt]]=ncnt; D[U[ncnt]]=ncnt; col[ncnt]=a; row[ncnt]=newr; size[a]++;
  U[++ncnt]=U[b]; D[ncnt]=b; U[D[ncnt]]=ncnt; D[U[ncnt]]=ncnt; col[ncnt]=b; row[ncnt]=newr; size[b]++;
  U[++ncnt]=U[c]; D[ncnt]=c; U[D[ncnt]]=ncnt; D[U[ncnt]]=ncnt; col[ncnt]=c; row[ncnt]=newr; size[c]++;
  U[++ncnt]=U[d]; D[ncnt]=d; U[D[ncnt]]=ncnt; D[U[ncnt]]=ncnt; col[ncnt]=d; row[ncnt]=newr; size[d]++;
}

#define P(x,y) (((x)-1)/3*3+((y)-1)/3+1)

int Map[10][10];
int ccnt[10][10],rcnt[10][10],gcnt[10][10];

inline void addnum(int x,int y,int k){
  ++newr; _x[newr]=x; _y[newr]=y; _k[newr]=k;
  addline((x-1)*9+y,81+(x-1)*9+k,81+81+(y-1)*9+k,81+81+81+(P(x,y)-1)*9+k);
}

int main(){
  char c; bool first=1;
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  while (read(c)){
    if (!first) putchar('\n'); first=0;
    Map[1][1]=c=='?'?-1:c-'0';
    for (int i=1;i<=9;i++)
      for (int j=1;j<=9;j++)
    if (i+j>2)
      read(c),Map[i][j]=c=='?'?-1:c-'0';
    for (int i=1;i<=9;i++)
      for (int j=1;j<=9;j++)
    if (~Map[i][j])
      rcnt[i][Map[i][j]]++,ccnt[j][Map[i][j]]++,gcnt[P(i,j)][Map[i][j]]++;
    for (int i=1;i<=324;i++) L[i]=i-1,R[i]=i+1,size[i]=0,U[i]=D[i]=i;
    ncnt=324; 
    R[0]=1; L[0]=324; R[324]=0;
    for (int i=1;i<=9;i++)
      for (int j=1;j<=9;j++)
    if (~Map[i][j])
      addnum(i,j,Map[i][j]);
    else{
      for (int k=1;k<=9;k++)
        if (!rcnt[i][k] && !ccnt[j][k] && !gcnt[P(i,j)][k])
          addnum(i,j,k);
    }
    dance();
    for (int i=1;i<=pnt;i++)
      Map[_x[ans[i]]][_y[ans[i]]]=_k[ans[i]];
    for (int i=1;i<=9;i++) for (int j=1;j<=9;j++) putchar(Map[i][j]+'0'),putchar(j==9?'\n':' ');
    newr=pnt=0;
    for (int i=1;i<=9;i++) for (int j=1;j<=9;j++) rcnt[i][j]=ccnt[i][j]=gcnt[i][j]=0;
  }
  return 0;
}