靶形数独 Editional
I-靶形数独_Part1.3 基础算法-深搜的剪枝技巧
https://ac.nowcoder.com/acm/contest/952/I
深搜+剪枝
计算方格(x,y)所在小九宫格的公式：(x-1)/3*3+(y-1)/3+1
方格的分值直接用一个数组储存
剪枝：玩过数独的人应该知道，我们需要从未知数字少的一行开始填，所以先按照每一行已知数的数目从大到小排序，先处理已知数多的行
用三维数组vis中的
vis[0][line][i]表示第line行的i是否被取过;
vis[1][column][i]表示第column列的i是否被取过;
vis[3][palace][i]表示第palace个小九宫格的i是否被取过.
Code:
#include <bits/stdc++.h>
using namespace std;
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 mp[15][15];
int vis[4][15][15];
struct node{
int cnt,id;
}a[15];
int palace(int x,int y)
{
return (x-1)/3*3+(y-1)/3+1;
}
bool cmp(node x,node y){return x.cnt>y.cnt;}
int tot=1,ans=0,sum=-1;
void dfs(int line,int column)
{
if(tot>=10)
{
sum=max(sum,ans);
return ;
}
if(column==10)
{
tot++;
dfs(a[tot].id,1);
tot--;
return ;
}
if(!mp[line][column])
{
for(int i=1;i<=9;i++)
{
if(vis[0][line][i] || vis[1][column][i] || vis[2][palace(line,column)][i])continue;
vis[0][line][i]=1;
vis[1][column][i]=1;
vis[2][palace(line,column)][i]=1;
mp[line][column]=i;
ans+=i*score[line][column];
dfs(line,column+1);
vis[0][line][i]=0;
vis[1][column][i]=0;
vis[2][palace(line,column)][i]=0;
mp[line][column]=0;
ans-=i*score[line][column];
}
}
else dfs(line,column+1);
return;
}
int main()
{
for(int i=1;i<=9;i++)
{
a[i].id=i;
for(int j=1;j<=9;j++)
{
cin>>mp[i][j];
if(mp[i][j]!=0)
{
vis[0][i][mp[i][j]]=1;
vis[1][j][mp[i][j]]=1;
vis[2][palace(i,j)][mp[i][j]]=1;
a[i].cnt++;ans+=mp[i][j]*score[i][j];
}
}
}
sort(a+1,a+10,cmp);
dfs(a[1].id,1);
cout<<sum<<endl;
return 0;
} 
查看16道真题和解析
