NOIP2009靶形数独[DFS 优化]

描述

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他
们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z博士请教，
Z 博士拿出了他最近发明的“靶形数独” ，作为这两个孩子比试的题目。
靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格
高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些
数字，利用逻辑推理，在其他的空格上填入 1到 9 的数字。每个数字在每个小九宫格内不能
重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即
每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）

上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红
色区域）每个格子为 9 分，再外面一圈（蓝色区域）每个格子为 8分，蓝色区域外面一圈（棕
色区域）每个格子为 7分，最外面一圈（白色区域）每个格子为 6 分，如上图所示。比赛的
要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取
更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字
的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 2829。游
戏规定，将以总分数的高低决出胜负。

由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能
够得到的最高分数。

格式

输入格式

一共 9 行。每行 9 个整数（每个数都在 0—9 的范围内），表示一个尚未填满的数独方
格，未填的空格用“0”表示。每两个数字之间用一个空格隔开。

输出格式

输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1。

样例1

样例输入1[复制]

7 0 0 9 0 0 0 0 1 
1 0 0 0 0 5 9 0 0 
0 0 0 2 0 0 0 8 0 
0 0 5 0 2 0 0 0 3 
0 0 0 0 0 0 6 4 8 
4 1 3 0 0 0 0 0 0 
0 0 7 0 0 2 0 9 0 
2 0 1 0 6 0 8 0 4 
0 8 0 5 0 4 0 1 2

样例输出1[复制]

样例2

样例输入2[复制]

0 0 0 7 0 2 4 5 3 
9 0 0 0 0 8 0 0 0 
7 4 0 0 0 5 0 1 0 
1 9 5 0 8 0 0 0 0 
0 7 0 0 0 0 0 2 5 
0 3 0 5 7 9 1 0 8 
0 0 0 6 0 1 0 0 0 
0 6 0 9 0 0 0 0 1 
0 0 0 0 0 0 0 0 6

样例输出2[复制]

限制

每个测试点2s

提示

40%的数据，数独中非 0数的个数不少于 30。
80%的数据，数独中非 0数的个数不少于 26。
100%的数据，数独中非 0 数的个数不少于 24。

来源

NOIP 2009

搜索每个位置填什么就可以了，用r,l,c分别判断行列九宫格是否合法

据说卡正序，可以倒过来

注释掉的那块按普通的顺序一行行搜

没注释掉的dfs配合了getnxt，得到当前可能填的方案最少的格子，从这个格子开始

//
//  main.cpp
//  noip2009靶形数独
//
//  Created by Candy on 10/2/16.
//  Copyright © 2016 Candy. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
//#define dfsnxt(x,y) y==9?dfs(x+1,1):dfs(x,y+1)
const int N=11;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x;
}
int a[N][N];
int r[N][N],l[N][N],c[N][N],score=0,ans=0;
int vis[N][N];
inline int id(int x,int y){return (x-1)/3*3+(y-1)/3+1;}
int v[9][9] = {
    {6, 6, 6, 6,  6, 6, 6, 6, 6},
    {6, 7, 7, 7,  7, 7, 7, 7, 6},
    {6, 7, 8, 8,  8, 8, 8, 7, 6},
    {6, 7, 8, 9,  9, 9, 8, 7, 6},
    {6, 7, 8, 9, 10, 9, 8, 7, 6},
    {6, 7, 8, 9,  9, 9, 8, 7, 6},
    {6, 7, 8, 8,  8, 8, 8, 7, 6},
    {6, 7, 7, 7,  7, 7, 7, 7, 6},
    {6, 6, 6, 6,  6, 6, 6, 6, 6}
};
inline int mark(int x,int y){return v[x-1][y-1];}
inline bool fil(int x,int y,int k){
    if(r[x][k]||l[y][k]||c[id(x,y)][k]) return 0;
    r[x][k]=l[y][k]=c[id(x,y)][k]=1;
    score+=k*mark(x,y);
    vis[x][y]=1;
    return 1;
}
inline void del(int x,int y,int k){
    r[x][k]=l[y][k]=c[id(x,y)][k]=0;
    score-=k*mark(x,y);
    vis[x][y]=0;
}
void getnxt(int &x,int &y){
    int mn=10,flag=0;
    for(int i=1;i<=9;i++)
        for(int j=1;j<=9;j++) if(!vis[i][j]){flag=1;
            int cnt=0;
            for(int k=1;k<=9;k++)
                if(!r[i][k]&&!l[j][k]&&!c[id(i,j)][k]) cnt++;
            if(cnt<mn){mn=cnt;x=i;y=j;}
        }
    if(!flag){x=0;y=0;}
}
//void dfs(int x,int y){
//    if(x==10){ans=max(ans,score);return;}
//    if(a[x][y]) dfsnxt(x,y);
//    else{
//        for(int i=1;i<=9;i++)
//            if(fil(x,y,i)){
//                dfsnxt(x,y);
//                del(x,y,i);
//            }
//    }
//}
void dfs(int x,int y){
    if(x==0&&y==0){ans=max(ans,score);return;}
    for(int i=1;i<=9;i++)
        if(fil(x,y,i)){
            int tx=1,ty=1; getnxt(tx,ty);
            dfs(tx,ty);
            del(x,y,i);
        }
}

int main(int argc, const char * argv[]) {
    for(int i=9;i>=1;i--)
        for(int j=9;j>=1;j--){a[i][j]=read();if(a[i][j]) fil(i,j,a[i][j]);}
    int x=1,y=1;getnxt(x,y);
    dfs(x,y);
    if(ans==0) printf("-1");
    else printf("%d",ans);
    return 0;
}