Sudoku

POJ 数据弱

POJ 数据强

题意:数独不解释了.两道题的输入输出有点差别,自己看一下题面.

分析:对每一行,每一列,每个格子都用一个九位的二进制数表示,初始化每一位都为1,然后每一次从状态最少的开始搜索,对于一个点\((i,j)\),\(val=line[i]\)&\(lie[j]\)&\(ge[(i/3)*3+j/3]\),则val是可以填的.

下面放的是3074的代码.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int hang[10],lie[10],ge[10],sum[1000];
char s[100],ch[10][10];
inline void get_bj(int x,int y,int z){
    hang[x]^=(1<<z);
    lie[y]^=(1<<z);
    ge[(x/3)*3+y/3]^=(1<<z);
}
inline bool dfs(int now){
    if(!now)return 1;//填完了
    int maxn=10,x,y;
    for(int i=0;i<9;++i)
        for(int j=0;j<9;++j){
            if(ch[i][j]!='.')continue;
            int val=hang[i]&lie[j]&ge[(i/3)*3+j/3];
            if(!val)return 0;//如果这一位要填数,却没东西填,则说明此次搜索失败
            if(sum[val]<maxn){//找到最少的可以填的地方
                maxn=sum[val];
                x=i;y=j;
            }
        }
    int val=hang[x]&lie[y]&ge[(x/3)*3+y/3];
    for(int j=0;j<9;++j)
        if(val&(1<<j)){
            ch[x][y]='1'+j;get_bj(x,y,j);
            if(dfs(now-1))return 1;
            ch[x][y]='.';get_bj(x,y,j);//回溯
        }
    return 0;
}
int main(){
    for(int i=0;i<(1<<9);++i)
        for(int j=0;j<9;++j)
            if(i&(1<<j))++sum[i];//预处理每个二进制数有几个1
    while(~scanf("%s",s)&&s[0]!='e'){
        for(int i=0;i<9;++i)
            for(int j=0;j<9;++j)ch[i][j]=s[i*9+j];
        for(int i=0;i<9;i++)hang[i]=lie[i]=ge[i]=(1<<9)-1;//初始化,每一位都为1
        int tot=0;
        for(int i=0;i<9;++i)
            for(int j=0;j<9;++j){
                if(ch[i][j]=='.')++tot;
                else get_bj(i,j,ch[i][j]-'1');
            }
        dfs(tot);//要填tot个格子
        for(int i=0;i<9;++i)
            for(int j=0;j<9;++j)s[i*9+j]=ch[i][j];
        puts(s);
    }
    return 0;
}

Sudoku

原文：https://www.cnblogs.com/PPXppx/p/11354615.html