luogu P1784 数独

HYLW · 2024-05-22 15:58:03 · 题解

#include<bits/stdc++.h>
using namespace std;
const int N = 11, M = 1<<N;
int g[N][N];

int gen[N];
int xl[N],yl[N],cub[5][5];
struct node{
    int x,y;
};
vector<node> q;
bool s[82];

void init(){
    for(int i=1;i<=9;i++)   gen[i]=1<<(i-1);

    for(int i=1;i<=9;i++)
        xl[i]=yl[i]=(1<<9)-1;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            cub[i][j]=(1<<9)-1;
}

int geten(int x){
    int s=0;
    while(x) x-=(x&-x),s++;
    return s;
}

void couten(int x){
    printf("--------\n");
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++)
            printf("%d ",g[i][j]);
        puts("");
    }
    printf("--------\n");
//  for(int i=8;i>=0;i--){
//      if(x&1<<i)  printf("1");
//      else    printf("0");    
//  }
//  printf(" ");
}

bool dfs(int u){
    if(!u)  return true;

    node k={-1,-1};
    int num=0x3f3f3f3f,h=0;
    for(int i=0;i<q.size();i++)
        if(!s[i]){
            int x=q[i].x,y=q[i].y;
            int t=xl[x]&yl[y]&cub[(x-1)/3+1][(y-1)/3+1];
            if(geten(t)<num){
                num=geten(t);k=q[i];h=i;
            }
        }
    s[h]=true;
    int st=xl[k.x]&yl[k.y]&cub[(k.x-1)/3+1][(k.y-1)/3+1];
    for(int i=8;i>=0;i--){
        if(st&1<<i){
            g[k.x][k.y]=i+1;
            xl[k.x]-=1<<i;
            yl[k.y]-=1<<i;
            cub[(k.x-1)/3+1][(k.y-1)/3+1]-=1<<i;

//          couten(1);

            if(dfs(u-1))    return true;

            xl[k.x]+=1<<i;
            yl[k.y]+=1<<i;
            cub[(k.x-1)/3+1][(k.y-1)/3+1]+=1<<i;
            g[k.x][k.y]=0;
        }
    }
    s[h]=false;
    return false;
}

int main(){
    init();
    for(int i=1;i<=9;i++)
        for(int j=1;j<=9;j++){
            scanf("%d",&g[i][j]);
            xl[i]-=gen[g[i][j]];
            yl[j]-=gen[g[i][j]];
            cub[(i-1)/3+1][(j-1)/3+1]-=gen[g[i][j]];
            if(g[i][j]==0)  q.push_back({i,j});
        }
//  for(int i=0;i<q.size();i++)
//      printf("%d %d,%d\n",q[i].nu,q[i].x,q[i].y);

    if(dfs(q.size())){
        for(int i=1;i<=9;i++){
            for(int j=1;j<=9;j++)
                printf("%d ",g[i][j]);
            puts("");
        }
    }
    return 0;
}

看看这个 。