题意：给定一个99的数独，要求判断是否为简单数独。
数独：对于每一行每一列或者子方格内，只能填1~9这几个数，并且每个数字只能出现一次，比如说：
如果一个99的数独是简单数独的话，这个数独的解是独一无二的
也就是说，每次可以推导出一个点，这个点的值是确定的，直到数独被填满。
对于下图，x只能填2
对于下图，x只能填1
判断数独是否是简单数独。如果是输出1，不是输出0.
这道题坑爹，质疑标程写错，数据出错。
其实仔细思考一番可以发现使用位运算来做，因为只有9个数，那么我们可以使用9位二进制来代表该数是否已经使用，若已经使用则为1，否则为0
那么我们可以很容易得到一个01的状态，它其实是个整数。
显然，可以容易每个点的可以放置的状态，第i位为1说明该点可以放置i，否则不能放置，若该状态只能放置1个点，也就是二进制中1的个数为1，那么就必然放置该点。
(这题训练赛的时候没有A，还被队友嘲讽了一发，队友敲了20分钟就过了，我勒个擦！)
这个代码其实早就出来了，因为我两种情况都考虑到了，诡异的一直wa
代码1：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
int bs[10][10],h[10],l[10],tmp[10][10],xs[4][4];
int check(){
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
if(!bs[i][j])return 0;
return 1;
}
int count1(int x){
int cnt=0;
while(x>0){
x-=x&-x;
++cnt;
}
return cnt;
}
void print(int x){
for(int i=0;i<9;i++)
if((x>>i)&1)printf("%d ",i+1);
puts("");
}
const int X = (1<<9)-1;
int main()
{
int T;
scanf("%d",&T);
while(T--){
for(int i=1,x;i<=9;i++){
for(int j=1;j<=9;j++){
scanf("%d",&x);
if(x)bs[i][j]=(1<<(x-1));
else bs[i][j]=0;
}
}
int flag=0;
while(1){
if(check())break;
for(int i=1;i<=9;i++)h[i]=X,l[i]=X;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)xs[i][j]=X;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++){
h[i]&=~bs[i][j];l[j]&=~bs[i][j];xs[(i-1)/3+1][(j-1)/3+1]&=~bs[i][j];
}
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++){
if(bs[i][j])tmp[i][j]=X&bs[i][j];
else tmp[i][j]=X&h[i]&l[j]&xs[(i-1)/3+1][(j-1)/3+1];
}
int rcnt=0;
for(int i=1;i<=9&&!rcnt;i++)
for(int j=1;j<=9&&!rcnt;j++){
if(bs[i][j])continue;
int tx=tmp[i][j];
int ct=count1(tx);
if(ct==1){
bs[i][j]=tx;
++rcnt;
break;
}
for(int ii=(i-1)/3*3+1;ii<=((i-1)/3+1)*3;ii++){
for(int jj=(j-1)/3*3+1;jj<=((j-1)/3+1)*3;jj++){
if(ii!=i&&jj!=j)tx&=~tmp[ii][jj];
}
}
int tt=count1(tx);
if(tt==1){
bs[i][j]=tx;
++rcnt;
break;
}
}
if(rcnt==0){
flag=1;break;
}
}
printf("%d",!flag);
}
puts("");
return 0;
}
|
这个代码我无意中删掉部分，就过了，发现其中只考虑了第一种情况。
代码2：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
int bs[10][10],h[10],l[10],tmp[10][10],xs[4][4];
int check(){
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
if(!bs[i][j])return 0;
return 1;
}
int count1(int x){
int cnt=0;
while(x>0){
x-=x&-x;
++cnt;
}
return cnt;
}
void print(int x){
for(int i=0;i<9;i++)
if((x>>i)&1)printf("%d ",i+1);
puts("");
}
const int X = (1<<9)-1;
int main()
{
int T;
scanf("%d",&T);
while(T--){
for(int i=1,x;i<=9;i++){
for(int j=1;j<=9;j++){
scanf("%d",&x);
if(x)bs[i][j]=(1<<(x-1));
else bs[i][j]=0;
}
}
int flag=0;
while(1){
if(check())break;
for(int i=1;i<=9;i++)h[i]=X,l[i]=X;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)xs[i][j]=X;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++){
h[i]&=~bs[i][j];l[j]&=~bs[i][j];xs[(i-1)/3+1][(j-1)/3+1]&=~bs[i][j];
}
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++){
if(bs[i][j])tmp[i][j]=X&bs[i][j];
else tmp[i][j]=X&h[i]&l[j]&xs[(i-1)/3+1][(j-1)/3+1];
}
int rcnt=0;
for(int i=1;i<=9&&!rcnt;i++)
for(int j=1;j<=9&&!rcnt;j++){
if(bs[i][j])continue;
int tx=tmp[i][j];
int ct=count1(tx);
if(ct==1){
bs[i][j]=tx;
++rcnt;
break;
}
}
if(rcnt==0){
flag=1;break;
}
}
printf("%d",!flag);
}
puts("");
return 0;
}
|
数据(需要能正确的推导出哪些点是一定的)：
0 8 0 3 0 0 0 0 9
0 0 0 0 8 0 0 0 3
3 0 0 5 0 0 0 8 2
1 9 8 4 5 7 3 2 6
5 2 3 9 6 1 8 4 7
4 7 6 2 3 8 1 9 5
9 3 4 8 2 5 7 6 1
6 5 2 0 0 4 9 3 8
8 1 7 6 9 3 2 5 4
7 8 0 3 0 0 0 0 9
0 0 0 0 8 0 0 0 3
3 0 0 5 0 0 0 8 2
1 9 8 4 5 7 3 2 6
5 2 3 9 6 1 8 4 7
4 7 6 2 3 8 1 9 5
9 3 4 8 2 5 7 6 1
6 5 2 0 0 4 9 3 8
8 1 7 6 9 3 2 5 4
1 6 0 0 0 0 7 0 0
0 0 0 0 0 1 0 0 0
0 0 0 4 0 9 0 0 0
0 0 0 0 3 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 8 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 7 0 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 6 0 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 2 3 0 0 0 0 0 0
4 5 6 0 0 0 0 0 0
7 8 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
|
