精确覆盖问题:在一个0-1矩阵中,选定部分行,使得每一列都有且只有一个1。求解一种选法

舞蹈链(Dance Link),也就是一个循环十字链表,可以快速的删掉和恢复某行某列

结合了舞蹈链的搜索就称作DLX算法

这里贴一个用DLX算法解决16×16数独的代码

9×9的直接暴力会更好

 // LA2659 Sudoku
// Rujia Liu
#include<cstdio>
#include<cstring>
#include<vector> using namespace std; const int maxr = ;
const int maxn = ;
const int maxnode = ; // 行编号从1开始,列编号为1~n,结点0是表头结点; 结点1~n是各列顶部的虚拟结点
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[maxr]; // 解 void init(int n) { // n是列数
this->n = n; // 虚拟结点
for(int i = ; i <= n; i++) {
U[i] = i; D[i] = i; L[i] = i-, R[i] = i+;
}
R[n] = ; L[] = n; sz = n + ;
memset(S, , sizeof(S));
} void addRow(int r, vector<int> columns) {
int first = sz;
for(int i = ; i < columns.size(); i++) {
int c = columns[i];
L[sz] = sz - ; R[sz] = sz + ; 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 - ] = first; L[first] = sz - ;
} // 顺着链表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;
} // d为递归深度
bool dfs(int d) {
if (R[] == ) { // 找到解
ansd = d; // 记录解的长度
return true;
} // 找S最小的列c
int c = R[]; // 第一个未删除的列
FOR(i,R,) if(S[i] < S[c]) c = i; remove(c); // 删除第c列
FOR(i,D,c) { // 用结点i所在行覆盖第c列
ans[d] = row[i];
FOR(j,R,i) remove(col[j]); // 删除结点i所在行能覆盖的所有其他列
if(dfs(d+)) return true;
FOR(j,L,i) restore(col[j]); // 恢复结点i所在行能覆盖的所有其他列
}
restore(c); // 恢复第c列 return false;
} bool solve(vector<int>& v) {
v.clear();
if(!dfs()) return false;
for(int i = ; i < ansd; i++) v.push_back(ans[i]);
return true;
} }; ////////////// 题目相关
#include<cassert> DLX solver; const int SLOT = ;
const int ROW = ;
const int COL = ;
const int SUB = ; // 行/列的统一编解码函数。从1开始编号
int encode(int a, int b, int c) {
return a*+b*+c+;
} void decode(int code, int& a, int& b, int& c) {
code--;
c = code%; code /= ;
b = code%; code /= ;
a = code;
} char puzzle[][]; bool read() {
for(int i = ; i < ; i++)
if(scanf("%s", puzzle[i]) != ) return false;
return true;
} int main() {
int kase = ;
while(read()) {
if(++kase != ) printf("\n");
solver.init();
for(int r = ; r < ; r++)
for(int c = ; c < ; c++)
for(int v = ; v < ; v++)
if(puzzle[r][c] == '-' || puzzle[r][c] == 'A'+v) {
vector<int> columns;
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/)*+c/, v));
solver.addRow(encode(r, c, v), columns);
} vector<int> ans;
assert(solver.solve(ans)); for(int i = ; i < ans.size(); i++) {
int r, c, v;
decode(ans[i], r, c, v);
puzzle[r][c] = 'A'+v;
}
for(int i = ; i < ; i++)
printf("%s\n", puzzle[i]);
}
return ;
}

最新文章

  1. 做为一名PHP程序员,应该关注的互联网IT大牛!
  2. 6、后记:PMO项目管理 - PMO项目管理办公室
  3. 黑马程序员——JAVA基础之抽象和接口 , 模版方法设计模式
  4. java集合框架复习(一)
  5. Webserver推送技术
  6. 关于debug和release 以及new 和delete
  7. tomcat解析之简单web服务器(图)
  8. H5前端面试题及答案(2)
  9. eclipse(Version: Mars.2 Release (4.5.2)) groovy plugin install process.
  10. Set集合判断对象重复的方法
  11. https请求抛出异常
  12. encodeURI、encodeURIComponent
  13. @Autowired 警告 Field injection is not recommended Spring @Autowired注入
  14. cdh 安装系列2--cdh manager product 安装
  15. TZOJ 1242 求出前m大的数(预处理)
  16. 利用python计算windows全盘文件md5值的脚本
  17. The file will have its original line endings in your working directory.
  18. electron 的中文文档的地址 以及 窗口改变的步骤
  19. PS_图象调整_太暗/过亮_曝光不足/过度
  20. 【Python项目篇】【爬妹子图】

热门文章

  1. 石家庄铁道大学网站首页UI分析
  2. OOP 1.4 内联函数和重载函数函数参数缺省值
  3. OOP 学习笔记汇总
  4. Servlet处理表单
  5. js登录界面代码自用
  6. 查询出menupath字段中 出现 “- &quot;(横杆)大于3次的 记录
  7. Mysql中的索引
  8. kettle、Oozie、camus、gobblin
  9. MySQL5.7 初使用
  10. 洛谷 P1495 曹冲养猪