青岛冠通市政建设有限公司网站,注册一个公司需要多久,seo优化视频教程,长沙景点必去本题思路来源于acwing算法提高课
题目描述 看本文需要准备的知识
1.dfs算法基本思想
2.位运算基础
3.对剪枝这个名词的大概了解
剪枝优化位运算优化
常见四种剪枝策略 首先考虑这道题的搜索顺序#xff0c;很明显#xff0c;可以随意选择一个空格子#xff0c;分支为这…本题思路来源于acwing算法提高课
题目描述 看本文需要准备的知识
1.dfs算法基本思想
2.位运算基础
3.对剪枝这个名词的大概了解
剪枝优化位运算优化
常见四种剪枝策略 首先考虑这道题的搜索顺序很明显可以随意选择一个空格子分支为这个空格子可以填入的所有数字然后对于每个分支可以再随意选择一个空格子继续进行上述步骤达成递归这种搜索顺序是一定能够把每一种情况不漏地搜索到
下面考虑优化的策略
第一个优化优化搜索顺序可以考虑一下什么情况下搜索的分支较少呢显然是对于那些可以填的数字合法情况比较少的空格所以我们再找下一个空格时就优先选择这类的空格
上面的搜索顺序保证了不会有冗余所以第二个剪枝策略用不上
第二个优化可行性剪枝就是说在遍历过程当中只考虑那些合法的数字分支即在那个空格的行、列以及九宫格上面不能有数字重复
最优性剪枝也是用不上的因为这里面只要找到一个合法解就行了不存在最优解的区分
第三个优化是位运算用来做两件事情
1.用一个9位的01串表示一行或一列或一个九宫格里面的填充情况0表示已经填充1表示没有填充举一个例子row[2]000111010表示第二行已经用过了9,8,7,3,1列col和九宫格cell同理那么对于一个坐标为(x,y)的空格怎么知道可以填哪些数字呢只需要把对应的row、col、cell进行与运算看一下1出现了第几位上那么就可以填几
2.lowbit优化
lowbit是什么是一个运算比如lowbit(x)x-x
lowbit可以算出什么比如10101可以得到1100100可以得到10011000可以得到1000注意上面的都是二进制数即得到最低位1的位置
有了lowbit之后对于一个空格假设我们通过上面二进制表示的行、列、九宫格的与运算得到了一个01串101001010这个01串有4个1如果直接遍历每次都要9次但是如果用上lowbit只需要遍历4次即可
lowbit(101001010)10第2位的1所以可以放2
lowbit(101001000)1000,第4位的1所以可以放4
依次类推......
详细过程
讲解了本题的优化策略下面来详细介绍这道题的实现细节
首先定义6个数组
其中三个为int row[N],col[N],cell[N][N]存放对应位置的状态
第四个是int ones[1N],表示某一个数的二进制表示里面有几个1
第五个是int log2[1N],表示某一个数的以2为底的对数因为使用lowbit之后得到的是2的k次幂而这个k才是我们想要的代表1的位置所以我们预处理这个数组方便后续使用
第六个就是char str[100]代表所有的格子内容包括数字和小数点表示暂时没有填充这两种情况 然后再写四个辅助函数分别是initdrawget_statelowbit
init初始化所有格子暂时全部没有填过数字
draw在(x,y)这个格子上面填上数字tis_settrue或者去掉数字t(is_setfalse)
get_state:得到(x,y)上的行、列、九宫格的状态交集01串
lowbit上面已经讲解过了 然后我们来说一下main函数的内容
对于每一个样例init初始化然后遍历输入的str对方格进行填充如果遇到’.’那么就记录一下最终统计暂未填充的格子总数最后调用dfs最后输出str即可 最后我们说dfs如何写
首先参数cnt代表还剩几个空格没有填数当cnt0时直接返回true即可表示已经全部填充完毕。
然后寻找分支数最少的空格搜索顺序优化
找到之后通过get_state函数得到01串然后利用lowbit去得到这个01串中1的每个位置就是一个新的分支这个遍历之后返回false保证函数代码的完整性
完整代码
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N9,M1N;
int row[N],col[N],cell[N][N];
int ones[M],log2_map[M];
char str[100];
void init()
{for(int i0;iN;i)row[i]col[i](1N)-1;for(int i0;iN/3;i){for(int j0;jN/3;j)cell[i][j](1N)-1;}
}
void draw(int x,int y,int t,bool is_set)
{if(is_set)str[x*Ny]t1;else str[x*Ny].;int r1t;if(!is_set)r-r;row[x]-r;col[y]-r;cell[x/3][y/3]-r;
}
int lowbit(int x)
{return x-x;
}
int get_state(int x,int y)
{return row[x]col[y]cell[x/3][y/3];
}
bool dfs(int cnt)
{if(!cnt)return true;int minx10;int x,y;for(int i0;iN;i){for(int j0;jN;j){if(str[i*Nj].){int stateget_state(i,j);if(ones[state]minx){minxones[state];xi,yj;}}}}int stateget_state(x,y);for(int istate;i;i-lowbit(i)){int tlog2_map[lowbit(i)];draw(x,y,t,true);if(dfs(cnt-1))return true;draw(x,y,t,false);}return false;
}
int main()
{for(int i0;iN;i)log2_map[1i]i;for(int i0;i1N;i)for(int j0;jN;j)ones[i](ij)1;while(cinstr,str[0]!e){init();int cnt0;for(int i0,k0;iN;i){for(int j0;jN;j,k){if(str[k]!.){draw(i,j,str[k]-1,true);}else cnt;}}dfs(cnt);coutstrendl;}return 0;
}
