【题目链接】

http://poj.org/problem?id=3076

【算法】

将数独问题转化为精确覆盖问题,用Dancing Links求解

【代码】

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <stack>
#include <limits.h>
using namespace std;
#define MAXS 100000 struct info
{
int pos,val;
} a[MAXS]; int i,j,cnt;
int mat[][];
char s[]; inline int getRow(int pos)
{
return (pos - ) / + ;
}
inline int getCol(int pos)
{
return (pos - ) % + ;
}
inline int getGrid(int pos)
{
int x = getRow(pos),y = getCol(pos);
return (x - ) / * + (y - ) / + ;
}
struct DancingLinks
{
int n,m,step,size;
int U[MAXS],D[MAXS],L[MAXS],R[MAXS],Row[MAXS],Col[MAXS];
int H[MAXS],S[MAXS];
int ans[MAXS];
inline void init(int _n,int _m)
{
int i;
n = _n;
m = _m;
for (i = ; i <= m; i++)
{
S[i] = ;
U[i] = D[i] = i;
L[i] = i - ;
R[i] = i + ;
}
L[] = m; R[m] = ;
size = m;
for (i = ; i <= n; i++) H[i] = -;
}
inline void link(int r,int c)
{
size++;
Row[size] = r;
Col[size] = c;
S[c]++;
D[size] = D[c];
U[D[c]] = size;
U[size] = c;
D[c] = size;
if (H[r] < ) L[size] = R[size] = H[r] = size;
else
{
R[size] = R[H[r]];
L[R[H[r]]] = size;
L[size] = H[r];
R[H[r]] = size;
}
}
inline void Remove(int c)
{
int i,j;
R[L[c]] = R[c];
L[R[c]] = L[c];
for (i = D[c]; i != c; i = D[i])
{
for (j = R[i]; j != i; j = R[j])
{
D[U[j]] = D[j];
U[D[j]] = U[j];
S[Col[j]]--;
}
}
}
inline void Resume(int c)
{
int i,j;
for (i = U[c]; i != c; i = U[i])
{
for (j = L[i]; j != i; j = L[j])
{
D[U[j]] = j;
U[D[j]] = j;
S[Col[j]]++;
}
}
L[R[c]] = c;
R[L[c]] = c;
}
inline bool solve(int dep)
{
int i,j,c;
if (R[] == )
{
step = dep;
return true;
}
c = R[];
for (i = R[]; i != ; i = R[i])
{
if (S[i] < S[c])
c = i;
}
Remove(c);
for (i = D[c]; i != c; i = D[i])
{
ans[dep] = Row[i];
for (j = R[i]; j != i; j = R[j])
Remove(Col[j]);
if (solve(dep+)) return true;
for (j = L[i]; j != i; j = L[j])
Resume(Col[j]);
}
Resume(c);
return false;
}
} DLX; int main()
{ while (scanf("%s",s+) != EOF)
{
cnt = ;
memset(mat,,sizeof(mat));
for (i = ; i < ; i++) scanf("%s",s+i*+);
for (i = ; i <= ; i++)
{
if (s[i] != '-')
{
mat[][i] = ;
mat[][+(getRow(i)-)*+s[i]-'A'+] = ;
mat[][+(getCol(i)-)*+s[i]-'A'+] = ;
mat[][+(getGrid(i)-)*+s[i]-'A'+] = ;
} else
{
for (j = ; j <= ; j++)
{
cnt++;
mat[cnt][i] = ;
mat[cnt][+(getRow(i)-)*+j] = ;
mat[cnt][+(getCol(i)-)*+j] = ;
mat[cnt][+(getGrid(i)-)*+j] = ;
a[cnt] = (info){i,j};
}
}
}
DLX.init(cnt,);
for (i = ; i <= cnt; i++)
{
for (j = ; j <= ; j++)
{
if (mat[i][j])
DLX.link(i,j);
}
}
DLX.solve();
for (i = ; i < DLX.step; i++) s[a[DLX.ans[i]].pos] = 'A' + a[DLX.ans[i]].val - ;
for (i = ; i <= ; i++)
{
printf("%c",s[i]);
if (i % == ) printf("\n");
}
printf("\n");
} return ; }

最新文章

  1. iOS多线程之7.NSOperation的初识
  2. Android入门(一)
  3. freeswitch 使用mysql替换默认的sqlite
  4. 10 Things Every Java Programmer Should Know about String
  5. cookie的写入与读出
  6. poj.1703.Find them, Catch them(并查集)
  7. zookeeper 安装与配置
  8. cocos2dx win打包apk
  9. 黄聪:C#如何通过MeasureString、Graphics获取字符串的像素长度
  10. bzoj1443
  11. VC/MFC强制退出本进程自己,VC/MFC关闭自己
  12. vs里 .sln和.suo 文件
  13. [黑马程序员] I/O
  14. (转载)Oracle10g 数据泵导出命令 expdp 使用总结(一)
  15. VFS四大对象之三 struct dentry
  16. Linux第八节课学习笔记
  17. [linux]解析crontab
  18. HttpServetRequest读取body只能一次的问题
  19. Java 容器源码分析之 ArrayList
  20. 项目:《ssh框架综合项目开发视频》-视频目录和第六天的EasyUI简单讲解

热门文章

  1. html5——动画案例(太阳系)
  2. php用户注册常用检测、写入
  3. 14、Scala类型参数
  4. transition-分栏按钮动画
  5. 如何让 HTML 识别 string 里的 &#39;\n&#39; 并成功换行
  6. ORM 事务
  7. 5.terms搜索多个值以及多值搜索结果优化
  8. JSONP代码收藏
  9. saving snaps iteratively with for loop in Paraview
  10. Vue项目搭建及原理四