专栏文章
P10482 Sudoku2 题解
P10482题解参与者 3已保存评论 2
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @miqyifm4
- 此快照首次捕获于
- 2025/12/04 12:49 3 个月前
- 此快照最后确认于
- 2025/12/04 12:49 3 个月前
P10482 Sudoku2
蓝书上来的,看到没有人写 DFS 位运算常数优化,于是来写一下,帮助其他和我一样不会的蒟蒻
常数优化
对于每行、每列、每个九宫格,分别用一个 9 位二进制数(全局整数变量)保存哪些数字还可以填
对于每个位置,把它所在行、列、九宫格的 3 个二进制数做位与运算(&),就可以得到该位置能填哪些数,用 lowbit 运算就可以把能填的数字取出
当一个位置填上某数后,把该位置所在的行、列、九宫格记录的二进制数的对应位改为 0 ,即可更新当前状态;回溯时改回 1 即可还原现场。
——《算阶》
更多细节下见代码
CPP#include<iostream>
#define N (1 << 9)//如果写define位运算一定要记得写括号!!!
#define lowbit(x) (x & -x)
using namespace std;
int T,n,a[10][10];
int cnt[N],f[N],x[9],y[9],z[9];
char c;
int gon(int i,int j){//在第几个九宫格
return i / 3 * 3 + j / 3;
}
int get_cnt(int i){//二进制下有多少个1,即为可填的数字个数
int ans=0;
while(i) ans++ , i-=lowbit(i);
return ans;
}
void work(int i,int j,int v){
x[i] ^= (1<<v);//异或的成对变换的运用
y[j] ^= (1<<v);
z[gon(i,j)] ^= (1<<v);
}
bool dfs(int tot){
if(!tot)return true;//找到则返回
int t=10,nx,ny;
for(int i=0;i<=8;i++){
for(int j=0;j<=8;j++){
if(!a[i][j]){
int w = x[i] & y[j] & z[gon(i,j)];
if(cnt[w]<t) nx=i,ny=j,t=cnt[w];//找到能填数目最小的
}
}
}
int w=x[nx]&y[ny]&z[gon(nx,ny)];
while(w){
int now=f[lowbit(w)];
a[nx][ny]=now+1;
work(nx,ny,now);
if(dfs(tot-1)) return true;
a[nx][ny]=0;
work(nx,ny,now);//回溯
w-=lowbit(w);
}
return false;
}
int main(){
for(int i=0;i<N;i++){
cnt[i]=get_cnt(i);
}
for(int i=0;i<=8;i++){
f[1<<i]=i;
}
while(1){
int tot=0;
for(int i=0;i<=8;i++){
x[i]=y[i]=z[i]=N-1;
}
for(int i=0;i<=8;i++){
for(int j=0;j<=8;j++){
cin>>c;
if(c=='e'){
return 0;
}
else if(c=='.')
a[i][j]=0;
else{
a[i][j]=c-'0';
}
if(a[i][j]) work(i,j,a[i][j]-1);
else{
tot++;
}
}
}
if(dfs(tot)){
for(int i=0;i<=8;i++){
for(int j=0;j<=8;j++){
printf("%d",a[i][j]);
}
}
}
cout<<endl;
}
return 0;
}
相关推荐
评论
共 2 条评论,欢迎与作者交流。
正在加载评论...