AcWing 166. 数独
原题链接
中等
作者:
一只迷路的小A
,
2021-02-03 16:04:35
,
所有人可见
,
阅读 407
#include<bits/stdc++.h> //被万能头征服的小A
#define ll long long
using namespace std;
const int N=9;
int ones[1<<N],row[N],col[N],cell[3][3];
int ma[1<<N];
char str[100];
inline int lowbit(int x)
{
return x&-x;
}
inline void intin()
{
for(int i=0;i<N;i++)
{
ma[1<<i]=i;
col[i]=row[i]=(1<<N)-1;
}
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
cell[i][j]=(1<<N)-1;
}
inline int getw(int x,int y)
{
return row[x]&col[y]&cell[x/3][y/3];
}
inline bool dfs(int p)
{
if(!p)
return true;
int x,y,minx=10;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if(str[i*9+j]=='.'&&ones[getw(i,j)]<minx)
{
minx=ones[getw(i,j)];
x=i,y=j;
}
}
}
for(int j=getw(x,y);j>0;j-=lowbit(j))
{
int u=ma[lowbit(j)];
row[x]-=1<<u;
col[y]-=1<<u;
cell[x/3][y/3]-=1<<u;
str[9*x+y]='1'+u;
if(dfs(p-1))
return true;
row[x]+=1<<u;
col[y]+=1<<u;
cell[x/3][y/3]+=1<<u;
str[9*x+y]='.';
}
return false;
}
int main()
{
for(int i=0;i<1<<N;i++)
{
int s=0;
for(int j=i;j;j-=lowbit(j))
s++;
ones[i]=s;
}
while(~scanf("%s",str),str[0]!='e')
{intin();
int ans=0;
for(int i=0,k=0;i<N;i++)
for(int j=0;j<N;j++,k++)
if(str[k]!='.')
{
int x=str[k]-'1';
row[i]-=1<<x;
cell[i/3][j/3]-=1<<x;
col[j]-=1<<x;
}else ans++;
dfs(ans);
cout<<str<<endl;
}
}