AcWing 1613. 数独简单版
原题链接
简单
作者:
ustbweihy
,
2020-09-13 16:58:33
,
所有人可见
,
阅读 497
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=9;
int map[1<<N],ones[1<<N];//map 用来表示二进制的1对应第几位,例如100对应2 ones用来存储某一个二进制有几个1,
int row[N],col[N],block[3][3];//row 存放某一个的二进制表示,用来显示可用数字的情况,col\block同理
int cnt;//统计空白格子数
char str[10][10];
inline int lowbit(int x)
{
return x&-x;
}
inline int get(int x,int y)
{
//返回i行j列可用哪几个数字
return row[x]&col[y]&block[x/3][y/3];
}
void init()
{
//init 初始化,用于将row\col\block数组的每个数字都全置为1
for(int i=0;i<N;i++)
{
row[i]=(1<<N)-1;
col[i]=(1<<N)-1;
}
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
block[i][j]=(1<<N)-1;
}
}
}
bool dfs(int cnt)
{
if(!cnt) return true;//将所有空白格子填写完成的话,则true
int minv=10;
int x,y;//存放最少方案数的格子的横纵坐标
//先找到一个可放数字最少的格子
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if(str[i][j]=='.')
{
int s=ones[get(i,j)];
if(s<minv)
{
minv=s;
x=i,y=j;
}
}
}
}
//先给出可选方案的二进制表示
//找到目标格子之后开始模拟填数独
for(int i=get(x,y);i;i-=lowbit(i))
{
int t=map[lowbit(i)];//t为最后一位1对应的是第几位
row[x]-=1<<t;
col[y]-=1<<t;
block[x/3][y/3]-=1<<t;
str[x][y]='1'+t;
if(dfs(cnt-1)) return true;
row[x]+=1<<t;
col[y]+=1<<t;
block[x/3][y/3]+=1<<t;
str[x][y]='.';
}
return false;
}
int main()
{
//预处理一下map、ones数组
for(int i=0;i<1<<N;i++)
{
int s=0;
for(int j=i;j;j-=lowbit(j)) s++;
ones[i]=s;//统计i的二进制有多少个1
}
for(int i=0;i<N;i++)
{
map[1<<i]=i;
}
init();
int cnt=0; //!!!! 每次要置为1 因为有多组测试数据
for(int i=0;i<9;i++)
{
cin>>str[i];
}
for(int i=0,k=0;i<N;i++)
{
for(int j=0;j<N;j++,k++)
{
if(str[i][j]!='.')
{
int t=str[i][j]-'1';//把1~9 映射成0~8
row[i]-=1<<t;//i行 t位 不能取 置为0
col[j]-=1<<t;//j列 同理
block[i/3][j/3]-=1<<t;
}
else cnt++;
}
}
dfs(cnt);
for(int i=0;i<9;i++)
{
cout<<str[i]<<endl;
}
return 0;
}