首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。