ZOJ 3122 Sudoku 【舞蹈链】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<iomanip> 
#include<algorithm>
#include<vector>
#define INF 2e9
#define maxnode 100000

using namespace std;

struct DLX{
    int up[maxnode],down[maxnode],left[maxnode],right[maxnode];
    int row[maxnode],col[maxnode],s[1050],h[5000];
    int n,m,size,ansd,ans[5000];
    
    void init(int n1,int m1){
        n=n1; m=m1;
        for(int i=0;i<=m;i++){
            left[i] = i-1;
            right[i] = i+1;
            up[i] = down[i] = i;
            s[i]=0;
        }
        left[0]=m; right[m]=0;
        size=m;
        for(int i=1;i<=n;i++) h[i]=-1;
    }
    
    void link(int r,int c){
        row[++size]=r; col[size]=c;
        s[c]++;
        up[size]=up[c];
        down[size]=c;
        down[ up[c] ]=size;
        up[c]=size;
        
        if( h[r]==-1 ) left[size]=right[size]=h[r]=size;
        else{
            left[size]=left[h[r]];
            right[size]=h[r];
            right[left[h[r]]]=size;
            left[h[r]]=size;
        }
    }
    
    void remove(int c){
        //cout<<"!!! "<<c<<endl;
        right[left[c]]=right[c];
        left[right[c]]=left[c];
        for(int i=down[c];i!=c;i=down[i]){
            for(int j=right[i];j!=i;j=right[j]){
                up[down[j]]=up[j];
                down[up[j]]=down[j];
                s[ col[j] ]--; 
            }
        }
    }
    
    void resume(int c){
        right[left[c]]=c;
        left[right[c]]=c;
        for(int i=down[c];i!=c;i=down[i]){
            for(int j=right[i];j!=i;j=right[j]){
                up[down[j]]=j;
                down[up[j]]=j;
                s[ col[j] ]++;
            }
        }
    }
    
    bool dance(int d){
        if( right[0]==0 ) return true;
        int c=right[0];
            
        for(int i=c;i!=0;i=right[i]){
            if( s[i]<s[c] ) c=i;
        }
        
        remove(c);
        for(int i=down[c];i!=c;i=down[i]){
            ans[d] = row[i];//行的编号 
            for(int j=right[i];j!=i;j=right[j]) remove( col[j] );
            if( dance(d+1) ) return true;
            for(int j=left[i];j!=i;j=left[j]) resume( col[j] );
        }
        resume(c);
        
        return false;
    }
}dlx; 

struct node{
    int r,c,num;
    node(int r1=0,int c1=0,int n1=0): r(r1),c(c1),num(n1) {}
}biao[5000];

char board[17][17];

int main(){
    ios::sync_with_stdio(false);
    //A->1 P->16
    //1-256 这个格子里有没有数
    //256 + 1-256 这一行里有没有数字x
    //512 + 1-256 这一列里有没有数字x
    //768 + 1-256 这个宫里有没有数字x

    int ca=0;
    while(1){
        int count=0;
        dlx.init(5000,1024);
        for(int i=0;i<16;i++){
            if( scanf("%s",board[i])==EOF ) return 0;
            for(int j=0;j<16;j++){
                int r=i/4,c=j/4;
                int gong=r*4+c;
                if(board[i][j]==‘-‘){
                    for(int k=1;k<=16;k++){
                        count++;
                        dlx.link(count,i*16+j+1);
                        dlx.link(count,256+i*16+k);
                        dlx.link(count,512+j*16+k);
                        dlx.link(count,768+gong*16+k);
                        biao[count]=node(i,j,k);
                    }
                
                }
                else{
                    int num=int(board[i][j])-64;
                    count++;
                    dlx.link( count,i*16+j+1 );
                    dlx.link( count,256+i*16+num);
                    dlx.link( count,512+j*16+num);
                    dlx.link( count,768+gong*16+num );
                    biao[count]=node(i,num);
                }
            }
        }

        dlx.dance(0);
        for(int i=0;i<256;i++){
            node p=biao[ dlx.ans[i] ];
            board[ p.r ][ p.c ] = char(p.num+64);
        }
        
        if( ca++ ) cout<<endl;
        for(int i=0;i<16;i++){
            for(int j=0;j<16;j++) cout<<board[i][j];
            cout<<endl;
        }
    }
    
    return 0;    
}