洛谷P1074：https://www.luogu.org/problemnew/show/P1074
思路
这道题一看就是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[
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}};
int ans=-
1,k,maxn;
int map[
10][
10],q[
1010][
4];
bool x[
10][
10],y[
10][
10],z[
10][
10];
struct date
{
int no;
int zero;
}cnt[10];
bool cmp(date a,date b)
{
return a.zero<
b.zero;
}
int g(
int ii,
int jj)
//判断宫
{
if(ii<=
3)
{
if(jj<=
3)
return 1;
else if(jj<=
6)
return 2;
else return 3;
}
else if(ii<=
6)
{
if(jj<=
3)
return 4;
else if(jj<=
6)
return 5;
else return 6;
}
else
{
if(jj<=
3)
return 7;
else if(jj<=
6)
return 8;
else return 9;
}
}
void cinn()
{
for(
int i=
1;i<=
9;i++
)
{
cnt[i].no=i;
//记录行号
for(
int j=
1;j<=
9;j++
)
{
cin>>
map[i][j];
if(map[i][j]!=
0)
{
maxn+=map[i][j]*score[i][j];
//预算本来就有的分数
x[i][map[i][j]]=
1;
y[j][map[i][j]]=
1;
z[g(i,j)][map[i][j]]=
1;
//把行列宫记录
}
else
cnt[i].zero++;
//计算0的个数
}
}
}
void dfs(
int now,
int sum)
//now为队列中第几个点 sum为总分
{
if(now>k)
//如果队列中的每个点都被枚举过了
{
ans=max(sum,ans);
//找出最大值
return;
}
for(
int i=
1;i<=
9;i++)
//枚举数字
if(!x[q[now][
1]][i]&&!y[q[now][
2]][i]&&!z[q[now][
3]][i])
//如果行列宫均没有用过这个数字
{
x[q[now][1]][i]=y[q[now][
2]][i]=z[q[now][
3]][i]=
1;
//行列宫记录
map[q[now][
1]][q[now][
2]]=i;
//记录这个数字
dfs(now+
1,sum+score[q[now][
1]][q[now][
2]]*map[q[now][
1]][q[now][
2]]);
x[q[now][1]][i]=y[q[now][
2]][i]=z[q[now][
3]][i]=
0;
//还原操作
map[q[now][
1]][q[now][
2]]=
0;
}
}
int main()
{
cinn();
sort(1+cnt,
1+
9+cnt,cmp);
//排序
for(
int i=
1;i<=
9;i++
)
for(
int j=
1;j<=
9;j++
)
{
if(!
map[cnt[i].no][j])
{
q[++k][
1]=
cnt[i].no;
q[k][2]=
j;
q[k][3]=
g(cnt[i].no,j);
}
}
dfs(1,maxn);
cout<<
ans;
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9726490.html
相关资源：JAVA上百实例源码以及开源项目
