emm。。。挺秀的。。。挺神的?


每行,每列,每宫用一个二进制数表示选或没选的状态,刚开始设没选为1,然后更改状态的时候异或一下就好了;

这样可以通过lowbit取出每一个没有选过的数;(妙啊?

关于剪枝:每次选状态数最小的位置(就是能选择的数少的位置)去向下搜索(需要预处理出每个数代表的状态能选择的数)


记着把我的读入改了。。我的读入好像有问题。。。反正交上去就WA了,但scanf没事,,,,,麻烦大佬指明一下错误QAQ。。。

#include<cstdio>
#include<iostream>
#define lbt(x) (x&-x)
#define cal(i,j) ((i/3)*3+(j/3))
#define R register int
using namespace std;
inline void gstr(char* s) {
register char ch; while(isspace(ch=getchar()));
do *s++=ch; while(!isspace(ch=getchar()));
}
int h[],l[],e[],cnt[],lg[],tot;
char a[][];
inline void f(int i,int j,int x) {h[i]^=<<x,l[j]^=<<x,e[cal(i,j)]^=<<x;}
bool dfs(int crt) {
if(crt==) return true;
R tmp=,x,y;
for(R i=;i<;++i) for(R j=;j<;++j) {
if(a[i][j]!='.') continue;
R vl=h[i]&l[j]&e[cal(i,j)];
if(!vl) return false;
if(cnt[vl]<tmp) tmp=cnt[vl],x=i,y=j;//找到状态量最少的位置
} R vl=h[x]&l[y]&e[cal(x,y)];
for(;vl;vl-=lbt(vl)) { R z=lg[lbt(vl)];
a[x][y]=''+z; f(x,y,z);
if(dfs(crt-)) return true;
f(x,y,z); a[x][y]='.';
} return false;
}
signed main() {
for(R i=;i<<<;++i) for(R j=i;j;j-=lbt(j)) ++cnt[i];
for(R i=;i<;++i) lg[<<i]=i; register char s[];
while(gstr(s),s[]!='e') {
for(R i=;i<;++i) for(R j=;j<;++j) a[i][j]=s[i*+j];
for(R i=;i<;++i) h[i]=l[i]=e[i]=(<<)-; tot=;
for(R i=;i<;++i) for(R j=;j<;++j) if(a[i][j]!='.') f(i,j,a[i][j]-'');
else ++tot; dfs(tot);
for(R i=;i<;++i) for(R j=;j<;++j) s[i*+j]=a[i][j]; printf("%s\n",s);
}
}

2019.04.26

最新文章

  1. css3 transition属性
  2. 一场IT民工 与 人贩子 之间的战争 - 感受来自PostgreSQL的爱
  3. 【面试】输出&quot;蛇形&quot;矩阵
  4. iOS开发工程师面试题(一)
  5. 两种交换机配置模式,以配置基于端口划分的VLAN为例
  6. Android记录11-控制ExpandableListView展开和关闭
  7. 【HDOJ】1277 全文检索
  8. iOS数据持久化 -- Core Data-备用
  9. python函数与方法装饰器
  10. J2SE知识点摘记(二十四)
  11. linux组网笔记
  12. python - xml转excel
  13. js判断数组里是否有重复元素的方法
  14. prompt的工作原理
  15. B站弹幕姬(&#128020;)分析与开发(上篇)
  16. ThreadPoolExecutor使用详解
  17. vue中解决跨域问题
  18. [LeetCode&amp;Python] Problem 258. Add Digits
  19. 使用 Maven 来管理项目 &amp; 从 0 开始搭建 Maven 项目
  20. Windows8连接网络后自动弹出Bing解决方法

热门文章

  1. awk简要使用
  2. 关于fragment生命周期的两张图片
  3. php判断终端是手机还是电脑访问网站代码
  4. mybatis项目报错:java.sql.SQLException: ORA-00911: 无效字符 解决方法
  5. 吐槽下linq to sql的分页功能
  6. 主键primary key和唯一索引unique index
  7. (转)Linux网络协议栈(三)——网络设备(1)
  8. 算法Sedgewick第四版-第1章基础-008一用数组实现栈(泛型、可变大小)
  9. cf123E Maze
  10. 《Effective Java》第8章 通用程序设计