NOIP2009 靶形数独

大家好，欢迎来到IT知识分享网。

拿到这道题就直接想到了搜索，我们只需要在输入时保存每一行已经用了的数字和每一列已经用了的的数字，并且保存下每一个3×3的小格里已经用了的数字，然后搜索时避免这样的情况即可，下面是代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
bool heng[10][10],shu[10][10],xiao[4][4][10];
int a[10][10],mfen=-1;
int ba[10][10]=
    {
        {
  
  0,0,0,0,0,0,0,0,0,0},
        {
  
  0,6,6,6,6,6,6,6,6,6},
        {
  
  0,6,7,7,7,7,7,7,7,6},
        {
  
  0,6,7,8,8,8,8,8,7,6},
        {
  
  0,6,7,8,9,9,9,8,7,6},
        {
  
  0,6,7,8,9,10,9,8,7,6},
        {
  
  0,6,7,8,9,9,9,8,7,6},
        {
  
  0,6,7,8,8,8,8,8,7,6},
        {
  
  0,6,7,7,7,7,7,7,7,6},
        {
  
  0,6,6,6,6,6,6,6,6,6}
    };

void Search(int x,int y)
{
    if(x==9&&y==10){
        int now=0;
        for(int i=1;i<=9;i++)
            for(int j=1;j<=9;j++)
                now=now+ba[i][j]*a[i][j];
        mfen=max(mfen,now);
        return;
    }


    if(y==10)
        Search(x+1,1);

    if(a[x][y]!=0) Search(x,y+1);
    else for(int i=1;i<=9;i++){
        if(heng[x][i]==0&&shu[y][i]==0&&xiao[(x-1)/3][(y-1)/3][i]==0){
            a[x][y]=i;
            heng[x][i]=1;
            shu[y][i]=1;
            xiao[(x-1)/3][(y-1)/3][i]=1;
            Search(x,y+1);
            a[x][y]=0;
            heng[x][i]=0;
            shu[y][i]=0;
            xiao[(x-1)/3][(y-1)/3][i]=0;
        }
    }
    return;
}

int main()
{
// freopen("sudoku.in","r",stdin);
// freopen("sudoku.out","w",stdout);
    for(int i=1;i<=9;i++)
        for(int j=1;j<=9;j++){
            cin>>a[i][j];
            heng[i][a[i][j]]=1;
            shu[j][a[i][j]]=1;
            xiao[(i-1)/3][(j-1)/3][a[i][j]]=1;
        }
    Search(1,1);
    cout<<mfen;
    return 0;
}

可能大家发现了，提交之后这个代码只有70~80分，这时候就可以用一个神奇的操作，反着搜，可能这样就会提前确定一些情况然后就会少计算一点，就神奇的过了，代码中只需要将Search小小修改一下即可，那这个就请大家自己思考一下了。(抄代码的别想了)