建图:

  从1到16枚举所有的行、列上放的数。

代码:

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <cctype>
#include <time.h> using namespace std; const int INF = <<;
const int MAXN = ;
const int MAXNODE = ;
const int MAXR = ; struct DLX {
// 行编号从1开始,列编号为1~n,结点0是表头结点;结点1~n是各列顶部的虚拟结点
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) { //删除c列
L[R[c]] = L[c]; R[L[c]] = R[c];
for (int i = D[c]; i != c; i = D[i]) // 对于每一个c列不为0的所有行
for (int j = R[i]; j != i; j = R[j]) { //删除这一整行
U[D[j]] = U[j]; D[U[j]] = D[j]; S[col[j]]--;
}
} void restore(int c) { //回连c列
for (int i = U[c]; i != c; i = U[i])
for (int j = L[i]; j != i; j = L[j]) {
U[D[j]] = j; D[U[j]] = j; S[col[j]]++;
}
L[R[c]] = c; R[L[c]] = c;
} bool dfs(int d) { //d为递归深度
if (R[] == ) { //找到解
ansd = d; //记录解的长度
return true;
} //找S最小的C列
int c = R[]; //第一个未删除的列
for (int i = R[]; i != ; i = R[i]) if (S[i]<S[c]) c = i; remove(c); //删除第c列
for (int i = D[c]; i != c; i = D[i]) { //用结点i所在的行覆盖第c列
ans[d] = row[i];
for (int j = R[i]; j != i; j = R[j]) remove(col[j]); //删除节结点i所在行覆盖第c列
if (dfs(d+)) return true;
for (int j = L[i]; j != i; j = L[j]) restore(col[j]); // 恢复
}
restore(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;
}
}; const int SLOT = ;
const int ROW = ;
const int COL = ;
const int SUB = ; inline int encode(int a, int b, int c) {
return a* + b* + c + ;
} inline 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;
} DLX solver; int main() {
#ifdef Phantom01
freopen("LA2659.txt", "r", stdin);
#endif //Phantom01 int T= ; while (read()) {
if (T!=) puts(""); T++;
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;
if (!solver.solve(ans)) while () ; 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 : Reflection API
  2. [转载]socket下server端支持多客户端并发访问简单实现
  3. BZOJ 4269 再见Xor
  4. AFNnetworking快速教程,官方入门教程译
  5. libeXosip2(2-3) -- eXosip2 event API
  6. 【集训笔记】贪心算法【HDOJ1052 【HDOJ2037
  7. c++界面设计皮肤工具
  8. ASP.NET MVC + 百度富文本编辑器 + EasyUi + EntityFrameWork 制作一个添加新闻功能
  9. [河南省ACM省赛-第三届] 聪明的kk (nyoj 171)
  10. JavaScript设计模式(8)-装饰者模式
  11. 让你的代码量减少3倍!使用kotlin开发Android(三) 缩短五倍的Java Bean
  12. [Swift]LeetCode296. 最佳开会地点 $ Best Meeting Point
  13. day 22 二十二、面向对象导入、名称空间、类与对象
  14. docker服务各个模块
  15. Mac + PyCharm 安装 Opencv3 + python2.7
  16. Struts2 框架使用 核心以及其他详细配置
  17. Hello py
  18. python r(不进行转义)的用法
  19. lua lua_settable
  20. Python 创建线程的方法

热门文章

  1. 关于PageRank的总结
  2. HTML基础——网站友情链接显示页面
  3. 如何设置ASP.NET站点页面运行超时
  4. hiho 1572 - set.upper_bound,排序树
  5. vuecli的使用之项目中的文件
  6. js的onclick和jq的click以及on和bind的区别
  7. POJ-1743 Musical Theme 字符串问题 不重叠最长重复子串
  8. Django综合基础知识
  9. 学习《PythonWeb开发实战(董伟明)》中文PDF+源代码
  10. Linux 磁盘管理及分区