题解 P1784 【数独】

笃行 · 2017-10-05 18:18:26 · 题解

本题的搜索方式大致都差不多。

在这里考虑减少dfs的层数，用while跳过已知数位。

另外楼下有用对二进制补位的方式进行搜索的dalao，但是实现起来比较麻烦。根据二进制的思想，用二进制的第i位是0或1来表示数字是否已出现。

可以用 | 运算符进行标记，用 ^ 运算符去标记，用 & 运算符进行判重，这样只需要一维的数组。

注意。本题第一个点如果9->1枚举会比较慢，所以还是从1->9枚举，这样就可以0msA掉这道题。

#include<cstdio>
#define z(i) (1<<i)
#define g(x,y) (3*((x-1)/3)+(y-1)/3+1)
int h[10],l[10],s[10],f[10][10],ok,sum=81;
int read()
{
    int _=0,___=1;char __=getchar();
    while(__<'0'||__>'9'){if(__=='-')___=-1;__=getchar();}
    while(__>='0'&&__<='9'){_=_*10+__-'0';__=getchar();}
    return _*___;
}
void out()
{
    for(int i=1;i<=9;i++)
      {
          for(int j=1;j<=9;j++)
            printf("%d ",f[i][j]);
          printf("\n");
      }
}
void dfs(int x,int y,int tot)
{
    while(f[x][y])
      {
          y++;
          if(y>9) x++,y=1;
      }
    for(int i=1;i<=9;i++)
      {
          if(h[x]&z(i)||l[y]&z(i)||s[g(x,y)]&z(i)) continue;
          f[x][y]=i; h[x]|=z(i); l[y]|=z(i); s[g(x,y)]|=z(i);
          if(tot==sum) ok=1;
          else dfs(x,y,tot+1);
          if(ok) return ;
          f[x][y]=0; h[x]^=z(i); l[y]^=z(i); s[g(x,y)]^=z(i);
      }
}
int main()
{
    for(int i=1;i<=9;i++)
      for(int x,j=1;j<=9;j++)
        {
          f[i][j]=x=read();
          if(!x)continue;
          h[i]|=z(x); l[j]|=z(x); s[g(i,j)]|=z(x);
          sum--;
        }    
    dfs(1,1,1);
    out();
    return 0;
}