【[NOIP2009】靶形数独 题解(大概)

题目传送门:!点我传送!

题目再怎么看也就只是简单的数独(sudoku)而已,其实没比基本的数独难到哪去。

先从最基本的数独开始讲,在程序中做数独最经常还是用深搜(Depth First Search),在进行剪枝后再对种种可能进行一一搜索。对于剪枝的方法还是要从数独的规则入手:满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复。在此我们可以用数组通过统计每一行、每一列、每一个粗线宫中存在的数字在讨论剩余空格中数字的可能。个人在在每次dfs时会先找出可能的数字最少的点优先进行搜索,这样可以减少不少时间(也算是个不小的优化吧)。

在此题中我们用上述做法找到所以可能并把最大的ANS找出进行输出即是答案。

 



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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int L[10][10],H[10][10],A[10][10]; //列 行 area
int map[10][10],ANS=0;
 
int Area(int x,int y)  
{  
    return  (x-1)/3*3+(y+2)/3;  
}

int Abs(int x)  
{  
    return x > 0 ? x : -x;  
}
 
int Score(int x,int y)  
{  
     return 10-max(Abs(x-5),Abs(y-5));  
}

int boom = 0;
void start()
{
        for (int i = 1; i <= 9; i++)
        {
                for (int j = 1; j <= 9; j++)
                {
                        int k = Area(i, j);
                        if (map[i][j])
                        {
                                if (!H[i][map[i][j]]&&!L[j][map[i][j]]&&!A[k][map[i][j]])
                                {
                                        H[i][map[i][j]]=L[j][map[i][j]]=A[k][map[i][j]]=1;
                                }else
                                {
                                        boom = 1; return;
                                }
                        }
                }
        }
}


void dfs(int now)
{
        int g_max=0, minn=10, px, py;
        for (int i = 1; i <= 9; i++)
        {
                for (int j = 1; j <= 9; j++)
                {
                        if (map[i][j]) continue;
                        int num = 0, sd=0;
                        for (int k = 1; k <= 9; k++)
                        {
                                if (H[i][k] || L[j][k] || A[Area(i, j)][k]) continue;
                                num++; sd=k;
                        }
                        if (num == 0) return;
                        if (num < minn)
                        {
                                minn = num;
                                px=i; py =j;
                        }
                        g_max += sd*Score(i,j);
                }
        }
       
        if(g_max+now <= ANS)  return ;  
    if(g_max == 0)  
    {  
        boom=1;  
        ANS = max(ANS,now);  
        return ;  
    }  
       
        for (int k = 1; k <= 9; k++)
        {
                if (H[px][k] || L[py][k] || A[Area(px, py)][k]) continue;
               
                H[px][k] = L[py][k] = A[Area(px, py)][k] =1;
                map[px][py] = k;
               
                dfs(now+k*Score(px, py));
               
                map[px][py] = 0;
                H[px][k] = L[py][k] = A[Area(px, py)][k] =0;
        }
        return;
}

int main(void)
{
       
        for (int i = 1; i <= 9; i++)
          for (int j = 1; j <= 9; j++)
          {
                scanf("%d", &map[i][j]);
                ANS+=map[i][j]*Score(i,j);
          }
        start();
        if (boom)
        {
                printf("-1");
                return 0;
        }
        dfs(ANS);
        if (boom) printf("%d", ANS);
        else printf("-1");
}


	

发表评论

邮箱地址不会被公开。 必填项已用*标注