【NOIP2009】【codevs1174】靶形数独

problem

solution

codes

//(如果你玩数独会怎么填呢)......启发式:把能确定的填上
#include<iostream>
using namespace std;

const int score[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}
};

//r[i][j],第i行第j个数是否填过...row_cnt[i],第i行填了几个数
int a[11][11], row[11][11], col[11][11], area[11][11];
int row_cnt[11], col_cnt[11], cnt, ans=-1;
//得到(r,c)是第几个区域的
inline int id(int r, int c){ return (r-1)/3*3+(c-1)/3+1; }
//计算当前得分
inline int calc(){
    int sum = 0;
    for(int i = 1; i <= 9; i++)
        for(int j = 1; j <= 9; j++)
            sum += score[i][j]*a[i][j];
    return sum;
}

void dfs(int r, int c, int cc){
    if(cc == 81){
        ans = max(ans, calc());
        return ;
    }else for(int i = 1; i <= 9; i++){//尝试每个填数
        if(row[r][i]||col[c][i]||area[id(r,c)][i]) continue;
        row[r][i] = col[c][i] = area[id(r,c)][i] = 1;
        row_cnt[r]++;  col_cnt[c]++;
        a[r][c] = i;
        //找没有填的最少的行和列
        int tr, vr=-1, tc, vc=-1;
        for(int j = 1; j <= 9; j++)
            if(row_cnt[j]>vr && row_cnt[j]!=9)
                vr = row_cnt[tr=j];
        for(int j = 1; j <= 9; j++)
            if(col_cnt[j]>vc && !a[tr][j])//(r,c)未填数
                vc = col_cnt[tc=j];
        dfs(tr,tc,cc+1);
        row[r][i] = col[c][i] = area[id(r,c)][i] = 0;
        row_cnt[r]--;  col_cnt[c]--;
        a[r][c] = 0;
    }
}

int main(){
    //datein
    for(int i = 1; i <= 9; i++){
        for(int j = 1; j <= 9; j++){
            cin>>a[i][j];
            if(a[i][j]){
                //更新初始数据
                row[i][a[i][j]] = col[j][a[i][j]] = area[id(i,j)][a[i][j]] = 1;
                row_cnt[i]++;  col_cnt[j]++;  cnt++;
            }
        }
    }
    //找没有填的最少的行和列。
    int tr, vr=-1, tc, vc=-1;
    for(int i = 1; i <= 9; i++)
        if(row_cnt[i]>vr && row_cnt[i]!=9)
            vr = row_cnt[tr=i];
    for(int i = 1; i <= 9; i++)
        if(col_cnt[i]>vc && !a[tr][i])
            vc = col_cnt[tc=i];
    //dfs
    dfs(tr,tc,cnt);
    cout<<ans<<"\n";
    return 0;
}
  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80404361