【解题报告】洛谷P1074 靶形数独
题目链接
https://www.luogu.com.cn/problem/P1074
思路
大模拟+贪心
这道题目我们要填数独，如果要直接填的话，”复杂度肯定爆炸“
所以我们要贪心地去找应该填的列
比如，我们平常在自己手玩数独的时候，会去找填的比较多的行或者列去填，这样就好填一些，相对于这道题目而言，就是0比较少的行或者列去填
然后我们按照行0少的去填
所以先建立一个结构体，去统计一下每行有0的数量，然后按照从小到大的顺序排序
我们就先填0少的，然后以此去填，我们可以预处理一下填某一个位置的顺序，这里可以用一个一维数组就存下来，这就比较牛逼了
然后我们对于每个进行搜索，在搜索开始之前，我们还可以预处理在每个位置所在的行列和九宫格内已经存在的数字，然后这样就方便确认是否填了这个数字了，我们在枚举的时候直接枚举可以填的数字就可以了
这道题目的难点，在于dfs顺序的确定，我们需要进行预处理，这里的预处理方法也是比较好的，虽然也可以用结构体来干，但是这种似乎更加省空间？
这是一个小tip，但是我觉得用结构体的正确率更高一点，至少不至于就和行和列的计算问题
然后这个搜索每次弄完之后不用判断是否已经填完了，因为填到第81个数字必然填完了，所以这也是一个比较好的tip，值得吸取
这个大模拟消耗了我大约三个小时的时间，然后这还不是我自己做出来的，然后这种大模拟简直比较考察代码能力，然而我的代码能力如此差？不行！我要狂恋搜索和大模拟！！
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
115
116
117
118
119
120
121
122
123
124
125
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=20;
struct node{
int id,lcnt;
}row[maxn];
bool cmp(node x,node y)
{
return x.lcnt<y.lcnt;
}
struct dfn{
int x,y;
}s[10000];
int n=9;
int a[maxn][maxn],ans[maxn][maxn],sol;
bool flag;
bool f[maxn][maxn];
bool g[maxn][maxn];
bool h[maxn][maxn];
int dfn[maxn];
int get_g(int x,int y)
{
if(x>=1&&x<=3){
if(y>=1&&y<=3) return 1;
else if(y>=4&&y<=6) return 2;
else return 3;
}
if(x>=4&&x<=6){
if(y>=1&&y<=3) return 4;
else if(y>=4&&y<=6) return 5;
else return 6;
}
if(x>=7&&x<=9){
if(y>=1&&y<=3) return 7;
else if(y>=4&&y<=6) return 8;
else return 9;
}
}
int get_c(int x,int y)
{
if(x==1||y==1||x==9||y==9) return 6;
else if(x==2||y==2||x==8||y==8) return 7;
else if(x==3||y==3||x==7||y==7) return 8;
else if(x==4||y==4||x==6||y==6) return 9;
else return 10;
}
int calc()
{
int res=0;
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
res+=ans[i][j]*get_c(i,j);
}
return res;
}
void dfs(int now)
{
if(now==82)
{
flag=true;
sol=max(sol,calc());
return ;
}
int x=s[now].x;
int y=s[now].y;
if(a[x][y]==0)
{
for(int i=1;i<=9;i++)
{
int pos=get_g(x,y);
if(!f[x][i]&&!g[y][i]&&!h[pos][i])
{
ans[x][y]=i;
f[x][i]=g[y][i]=h[pos][i]=true;
dfs(now+1);
f[x][i]=g[y][i]=h[pos][i]=false;
}
}
}
else dfs(now+1);
}
int main()
{
for(int i=1;i<=9;i++)
{
int cnt=0;
for(int j=1;j<=9;j++)
{
cin>>a[i][j];
if(a[i][j]==0) cnt++;
else
{
int val=a[i][j];
int pos=get_g(i,j);
ans[i][j]=val;
f[i][val]=true;
g[j][val]=true;
h[pos][val]=true;
}
}
row[i].id=i;
row[i].lcnt=cnt;
}
sort(row+1,row+1+9,cmp);
int tot=0;
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
s[++tot].x=row[i].id;
s[tot].y=j;
}
}
dfs(1);
if(flag)
cout<<sol<<'\n';
else
cout<<-1<<'\n';
return 0;
}
|
