思路
就是一个填数独的小游戏
不会填数独的先去自己玩几把
众所周知，数独每一行、每一列、每一个3*3宫格内的数字均含1~9，且不重复
所以我们设三个数组r[10][10]，c[10][10]，block[10][10]
分别记录行、列、3*3宫格内数字的使用情况
重点：剪枝
我们知道，数独的玩法是先从已知数字多的一行/一列/宫格开始填，这样要枚举的数就少，更好填
剪枝也是这个思路
记录每一行 \(0\) 的个数，然后从小到大排序再dfs，这样dfs的层数会少很多
数据比较小，所以可以只按行排就行了
然后就是最简单的搜索与回溯啦
代码
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pc putchar
using namespace std;
template<typename T>
inline void read(T &x)
{
x=0;
T f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
while(isdigit(c)){x=x*10+(c^48); c=getchar();}
x*=f;
return;
}
template<typename T,typename... Args> inline void read(T &x, Args&... args){read(x); read(args...);}
template<typename Z>
inline void write(Z x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar((x%10)^48);
}
template<typename Z,typename... Args> inline void write(Z x, Args... args){write(x); putchar(' '); write(args...);}
const int N=10;
const int val[N][N] = {//方格分值
{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}
};
int id(int x,int y)//看哪个宫格需要计算一下
{
if(x<=3 && y<=3) return 1;
if(x<=3 && y<=6) return 2;
if(x<=3 && y<=9) return 3;
if(x<=6 && y<=3) return 4;
if(x<=6 && y<=6) return 5;
if(x<=6 && y<=9) return 6;
if(x<=9 && y<=3) return 7;
if(x<=9 && y<=6) return 8;
if(x<=9 && y<=9) return 9;
}
struct zer{
int line, cnt;
friend bool operator<(const zer& x, const zer& y){
return x.cnt < y.cnt;
}
}z[10];
int a[N][N];
ll ans;
bool r[N][N],c[N][N],block[N][N];//分别记录行、列、`3*3`宫格内数字的使用情况
void dfs(int pos,int x,int y)
{
if(pos == 10)//全搜完了
{
ll sum = 0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
sum += a[i][j] * val[i][j];//计算当前的数独的分数
ans = max(ans, sum);//取最大
return;
}
if(y == 10)
{
dfs(pos+1, z[pos+1].line, 1);//这一行填完了，递归到下一行
return;
}
if(a[x][y] == 0)//这个位置没填数
{
for(int num=1;num<=9;num++)
if(!r[x][num] && !c[y][num] && !block[ id(x,y) ][num])//可以填
{
r[x][num] = c[y][num] = block[ id(x,y) ][num] = 1;
a[x][y] = num;
dfs(pos, x, y+1);
a[x][y] = 0;//回溯
r[x][num] = c[y][num] = block[ id(x,y) ][num] = 0;
}
}
else //这个位置填上了，去下一个数
dfs(pos, x, y+1);
}
int main()
{
for(int i=1;i<=9;i++)
{
int cnt0 = 0;
for(int j=1;j<=9;j++)
{
read(a[i][j]);
if(a[i][j] == 0) cnt0++;//一行 0 的个数
r[i][a[i][j]] = 1;
c[j][a[i][j]] = 1;
block[ id(i,j) ][a[i][j]] = 1;
}
z[i] = {i, cnt0};
}
sort(z+1, z+10);//根据 0 的数量排序
dfs(1, z[1].line, 1);
write(ans);
return 0;
}