Open sx349 opened 4 years ago
#include<stdio.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
int a[9][9];
int heng[9],shu[9],blo[3][3];
int GG,t;
void dfs(int x,int y){
if(GG)return;
if(x==9){/*
rep(i,0,8){
rep(j,0,8)printf("%d ",a[i][j]);
putchar('\n');
}*/
t=a[0][0]*100+a[0][1]*10+a[0][2];
GG=1;
return;
}
if(y==9){
dfs(x+1,0);
return;
}
if(a[x][y]==0){
for(int G=heng[x]&shu[y]&blo[x/3][y/3];G;G-=G&-G){
a[x][y]=__builtin_ctz(G)+1;
heng[x]^=1<<__builtin_ctz(G);
shu[y]^=1<<__builtin_ctz(G);
blo[x/3][y/3]^=1<<__builtin_ctz(G);
dfs(x,y+1);
a[x][y]=0;
heng[x]|=1<<__builtin_ctz(G);
shu[y]|=1<<__builtin_ctz(G);
blo[x/3][y/3]|=1<<__builtin_ctz(G);
}
}else dfs(x,y+1);
}
char s[15][15];int Case;
signed main(){
freopen("testdata.in","r",stdin);
int ans=0;
while(~scanf("%s%d",s[0],&Case)){
GG=0;
rep(i,0,8)heng[i]=shu[i]=511;
rep(i,0,2)rep(j,0,2)blo[i][j]=511;
rep(i,0,8)scanf("%s",s[i]);
rep(i,0,8)rep(j,0,8)a[i][j]=s[i][j]-'0';
rep(i,0,8)rep(j,0,8)if(a[i][j])heng[i]^=1<<(a[i][j]-1);
rep(j,0,8)rep(i,0,8)if(a[i][j])shu[j]^=1<<(a[i][j]-1);
rep(i,0,8)rep(j,0,8)if(a[i][j])blo[i/3][j/3]^=1<<(a[i][j]-1);
dfs(0,0);
ans+=t;
printf("%d %d\n",Case,t);
}
printf("%d",ans);
}
https://pe-cn.github.io/96/
Problem 96 Su Doku Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar