POJ 3076 스 도 쿠 [DancingLinks, 게임]

#include<stdio.h>

#include<string.h>

const int MAX_COLOUMN = 16*16+16*16+16*16+16*16+2;//      

const int MAX_ROW = 16*16*16+2;//       



int cnt[MAX_COLOUMN];//cnt[i]   i 1   

int most,coloumn;

bool ans[MAX_ROW];//ans        

//       

struct Point

{

   int up,down,left,right;// ， ， ， 

   int coloumn;//       

   int row;//  

}node[MAX_ROW*MAX_COLOUMN+MAX_COLOUMN];



//          

void init(int m)

{

 int i;

 for(i=0;i<=m;i++)

 {

  node[i].down=i;

  node[i].up = i;

  node[i].coloumn=i;

  node[i].left=i-1;

  node[i].right=i+1;

  cnt[i]=0;

 }

 node[0].left = m;

 node[m].right = 0;

}



void remove(int c)//  c    1      

{

 node[node[c].right].left=node[c].left;

 node[node[c].left].right=node[c].right;

 int t,tt;

 for(t=node[c].down;t!=c;t=node[t].down)//                         

 {

  for(tt = node[t].right;tt!=t;tt=node[tt].right)//         

  {

            cnt[node[tt].coloumn]--;

   node[node[tt].down].up = node[tt].up;

   node[node[tt].up].down = node[tt].down;

  }

 }

}



void resume(int c)//  c    1      

{

 int t,tt;

 for(t=node[c].up;t!=c;t=node[t].up)//           c  1      

 {

  for(tt=node[t].left;tt!=t;tt=node[tt].left)

  {

   cnt[node[tt].coloumn]++;

   node[node[tt].up].down=tt;

   node[node[tt].down].up=tt;

  }

 }



 node[node[c].right].left=c;

 node[node[c].left].right=c;

}



bool dfs(int k)//k          

{

 int i,j;

 if(k>=most)return false;

 if(node[coloumn].right == coloumn)//        

 {

  if(k<most)

   most = k;

  return true;

 }



 int t = coloumn+1;

 int c;

 //       1    

 for(i=node[coloumn].right;i!=coloumn;i=node[i].right)

 {

  if(cnt[i]<t)

  {

   c=i;t=cnt[i];

   if(t==1)break;

  }

 }

    

 remove(c);//   c   1    



 //           ，       ，    

 for(i = node[c].down;i!=c;i=node[i].down)

 {

  for(j=node[i].right;j!=i;j=node[j].right)

  {

   remove(node[j].coloumn);

  }

  ans[node[j].row]=true;

  if(dfs(k+1))

  {

   return true;

  }

  ans[node[j].row]=false;

  for(j=node[j].left;j!=i;j=node[j].left)

  {

   resume(node[j].coloumn);

  }



  

 }



 resume(c);

 return false;

}

bool graph[MAX_ROW][MAX_COLOUMN];

void addrow(int i,int j,int k)

{

    int curr = (i*16+j)*16+k;

 graph[curr][(i*16+j)]=true;

 graph[curr][16*16+i*16+k]=true;

 graph[curr][16*16+16*16+j*16+k]=true;

    int tr = i/4;

 int tc = j/4;

 graph[curr][16*16+16*16+16*16+(tr*4+tc)*16+k]=true;

}



char str[MAX_ROW];

int main()

{

 int N,M,i,j,k;



 while(true)

  {

   //printf("%s",str);

  N=16*16*16;

  M = 16*16+16*16+16*16+16*16;

  coloumn = M;

  int cur=coloumn+1;//      

  init(coloumn);

  memset(graph,0,sizeof(graph));

  for(i=0;i<16;i++)

  {

   

   if(scanf("%s",str)!=1)return 0;

   for(j=0;j<16;j++)

   {

    if(str[j]=='-')

    {

     for(k=0;k<16;k++)//       

     {

       addrow(i,j,k);

     }

     continue;

    }

    k = str[j]-'A';

       addrow(i,j,k);

   }

  }

  for(i=0;i<N;i++)

  {

   int start = cur;//   i       

   int pre = cur;//       1      1  

   for(j=0;j<M;j++)

   {

   // scanf("%d",&n);

    if(graph[i][j])//        0  

    {

     int pos = j;

     node[cur].up = node[pos].up;

     node[node[pos].up].down = cur;

        node[cur].down = pos;

     node[pos].up = cur;

     cnt[pos]++;//  1   +1

     node[cur].coloumn = pos;

     node[cur].left = pre;

     node[pre].right = cur;

     node[cur].right = start;

                    node[start].left=cur;

     node[cur].row = i;

     pre=cur++;

    }

   }

  }



 

  most = N+1;//           

  memset(ans,false,sizeof(ans));

  dfs(0);

  // printf("Yes, I found it
");

  for(i=0;i<16*16;i++)

  { 

   if(i!=0&&i%16==0)printf("
");

   for(j=0;j<16;j++)

    if(ans[i*16+j])

    {

     printf("%c",j+'A');

     break;

    }

   

  }



    printf("

");

  }

 

 return 0;

}