A. 「NOIP2009」靶形数独
暴搜。
本着搜索必剪枝的思想，略微做一点优化：优先搜索 \(0\) 少的行。
然后就搜就行。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
namespace IO{
const int sz=1<<20;
char in[sz],*p1=in,*p2=in;
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,sz,stdin),p1==p2)?EOF:*p1++)
template<typename T=int>il int read(){
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
T x=0;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
#undef getchar
char out[1<<20],*p3=out,s[50];
il int flush(){
fwrite(out,1,p3-out,stdout);
p3=out;
return 0;
}
#define putchar(ch) (p3==out+sz&&flush(),*p3++=(ch))
template<typename T>il void write(T x,bool typ=1){
int top=0;
if(x<0){
putchar('-');
x=-x;
}
do{
s[++top]=x%10|48;
x/=10;
}while(x);
while(top){
putchar(s[top--]);
}
putchar(typ?'\n':' ');
}
#undef putchar
}
using IO::read;
using IO::write;
const int hao[15][15]={{},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9}};
const int sco[15][15]={{},
{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 a[15][15],ans=-1;
int p[15],cnt[15],b[105];
bool vis[3][15][15];
il int cal(){
int res=0;
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
res+=a[i][j]*sco[i][j];
}
}
return res;
}
il void dfs(int u){
if(u==82){
ans=max(ans,cal());
return ;
}
int x=b[u]/10,y=b[u]%10;
// cout<<x<<" "<<y<<"\n";
if(a[x][y]){
dfs(u+1);
return ;
}
for(int i=1;i<=9;i++){
if(!vis[0][x][i]&&!vis[1][y][i]&&!vis[2][hao[x][y]][i]){
a[x][y]=i;
vis[0][x][i]=1;
vis[1][y][i]=1;
vis[2][hao[x][y]][i]=1;
dfs(u+1);
a[x][y]=0;
vis[0][x][i]=0;
vis[1][y][i]=0;
vis[2][hao[x][y]][i]=0;
}
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
for(int i=1;i<=9;i++){
p[i]=i;
for(int j=1;j<=9;j++){
a[i][j]=read();
if(a[i][j]){
vis[0][i][a[i][j]]=1;
vis[1][j][a[i][j]]=1;
vis[2][hao[i][j]][a[i][j]]=1;
}
else{
cnt[i]++;
}
}
}
sort(p+1,p+10,[](const int &x,const int &y){return cnt[x]<cnt[y];});
for(int i=1,x,tot=0;i<=9;i++){
x=p[i];
for(int y=1;y<=9;y++){
b[++tot]=x*10+y;
}
}
// for(int i=1;i<=81;i++){
// cout<<b[i]<<" ";
// }
// puts("");
dfs(1);
write(ans);
IO::flush();
return 0;
}
}
int main(){return asbt::main();}