思路
这道题一看就是DFS
打一个分数表方便后面算分
我用x y z数组分别表示行 列 宫 是否有放置数字
用cnt结构体中no和zero分别表示每行行号和每行的零的数量（下面会讲到为什么）
我们把每行按照零的数量从小到大排序 并保留行号来计算（因为搜索的层数与每行0的个数有关）
我们用一个队列q表示有几个点要枚举
然后我们从零最少的那行开始枚举就ok了
PS：ans一开始要赋值为-1 因为有无解的情况要输出-1（没有判无解的话95分 别问我咋知道的）
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int score[][]=
{{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,}};
int ans=-,k,maxn;
int map[][],q[][];
bool x[][],y[][],z[][];
struct date
{
int no;
int zero;
}cnt[];
bool cmp(date a,date b)
{
return a.zero<b.zero;
}
int g(int ii,int jj)//判断宫
{
if(ii<=)
{
if(jj<=) return ;
else if(jj<=) return ;
else return ;
}
else if(ii<=)
{
if(jj<=) return ;
else if(jj<=) return ;
else return ;
}
else
{
if(jj<=) return ;
else if(jj<=) return ;
else return ;
}
}
void cinn()
{
for(int i=;i<=;i++)
{
cnt[i].no=i;//记录行号
for(int j=;j<=;j++)
{
cin>>map[i][j];
if(map[i][j]!=)
{
maxn+=map[i][j]*score[i][j];//预算本来就有的分数
x[i][map[i][j]]=;
y[j][map[i][j]]=;
z[g(i,j)][map[i][j]]=;//把行列宫记录
}
else
cnt[i].zero++;//计算0的个数
}
}
}
void dfs(int now,int sum)//now为队列中第几个点 sum为总分
{
if(now>k)//如果队列中的每个点都被枚举过了
{
ans=max(sum,ans);//找出最大值
return;
}
for(int i=;i<=;i++)//枚举数字
if(!x[q[now][]][i]&&!y[q[now][]][i]&&!z[q[now][]][i])//如果行列宫均没有用过这个数字
{
x[q[now][]][i]=y[q[now][]][i]=z[q[now][]][i]=;//行列宫记录
map[q[now][]][q[now][]]=i;//记录这个数字
dfs(now+,sum+score[q[now][]][q[now][]]*map[q[now][]][q[now][]]);
x[q[now][]][i]=y[q[now][]][i]=z[q[now][]][i]=;//还原操作
map[q[now][]][q[now][]]=;
}
}
int main()
{
cinn();
sort(+cnt,++cnt,cmp);//排序
for(int i=;i<=;i++)
for(int j=;j<=;j++)
{
if(!map[cnt[i].no][j])
{
q[++k][]=cnt[i].no;
q[k][]=j;
q[k][]=g(cnt[i].no,j);
}
}
dfs(,maxn);
cout<<ans;
}