首页 > 代码库 > POJ 3076

POJ 3076

DLX算法,刚接触,是关于精确覆盖的,白书上有算法介绍。

代码模板

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string.h>#include <vector>using namespace std;char puzzle[20][20];const int SLOT=0;const int ROW=1;const int COL=2;const int SUB=3;const int maxn=1300;const int maxnode=256*16*4;const int maxr=256*16*4;struct DLX{  int n , sz;                                                 // 行数,节点总数  int S[maxn];                                                // 各列节点总数  int row[maxnode],col[maxnode];                              // 各节点行列编号  int L[maxnode],R[maxnode],U[maxnode],D[maxnode];            // 十字链表  int ansd,ans[maxn];                                         // 解  void init(int n )  {    this->n = n ;    for(int i = 0 ; i <= n; i++ )    {      U[i] = i ;      D[i] = i ;      L[i] = i - 1;      R[i] = i + 1;    }    R[n] = 0 ;    L[0] = n;    sz = n + 1 ;    memset(S,0,sizeof(S));  }  void addRow(int r,vector<int> c1)  {    int first = sz;    for(int i = 0 ; i < c1.size(); i++ ){      int c = c1[i];      L[sz] = sz - 1 ; R[sz] = sz + 1 ; D[sz] = c ; U[sz] = U[c];      D[U[c]] = sz; U[c] = sz;      row[sz] = r; col[sz] = c;      S[c] ++ ; sz ++ ;    }    R[sz - 1] = first ; L[first] = sz - 1;  }  // 顺着链表A,遍历除s外的其他元素  #define FOR(i,A,s) for(int i = A[s]; i != s ; i = A[i])  void remove(int c){    L[R[c]] = L[c];    R[L[c]] = R[c];    FOR(i,D,c)      FOR(j,R,i) {U[D[j]] = U[j];D[U[j]] = D[j];--S[col[j]];}  }  void restore(int c){    FOR(i,U,c)      FOR(j,L,i) {++S[col[j]];U[D[j]] = j;D[U[j]] = j; }    L[R[c]] = c;    R[L[c]] = c;  }  bool dfs(int d){    if(R[0] == 0 ){      ansd = d;      return true;    }    // 找S最小的列c    int c = R[0] ;    FOR(i,R,0) if(S[i] < S[c]) c = i;    remove(c);    FOR(i,D,c){      ans[d] = row[i];      FOR(j,R,i) remove(col[j]);      if(dfs(d + 1)) return true;      FOR(j,L,i) restore(col[j]);    }    restore(c);    return false;  }  bool solve(vector<int> & v){    v.clear();    if(!dfs(0)) return false;    for(int i = 0 ; i< ansd ;i ++ ) v.push_back(ans[i]);    return true;  }};DLX slover;int encode(int a,int b,int c){	return a*256+b*16+c+1;}void decode(int code,int &a,int &b,int &c){	code--;	c=code%16; code/=16;	b=code%16; code/=16;	a=code;}bool read(){	for(int i=0;i<16;i++){		if(scanf("%s",puzzle[i])!=1) return false;	}	return true;}int main(){	int kase=0;	while(read()){		if(++kase!=1) printf("\n");		slover.init(1024);		for(int r=0;r<16;r++){			for(int c=0;c<16;c++){				for(int v=0;v<16;v++){					if(puzzle[r][c]==‘-‘||puzzle[r][c]==‘A‘+v){						vector<int> columns;						columns.clear();						columns.push_back(encode(SLOT,r,c));						columns.push_back(encode(ROW,r,v));						columns.push_back(encode(COL,c,v));						columns.push_back(encode(SUB,(r/4)*4+c/4,v));						slover.addRow(encode(r,c,v),columns);					}				}			}		}		vector<int>ans;	//	cout<<"YES"<<endl;		ans.clear();		slover.solve(ans);	//	cout<<"YES"<<endl;		for(int i=0;i<ans.size();i++){			int r,c,v;			decode(ans[i],r,c,v);			puzzle[r][c]=‘A‘+v;		}		for(int i=0;i<16;i++)		printf("%s\n",puzzle[i]);	}	return 0;}

  

POJ 3076