AcWing 183. 靶形数独
原题链接
中等
作者:
ZTEG
,
2019-11-18 21:51:37
,
所有人可见
,
阅读 1356
O2优化他不香吗?
O3优化他不香吗?
绝对不是我懒得打正解优化
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int MAP[15][15],ans;
int a[15][15];
ll x[15],y[15],k[15];
int fk(int x,int y)
{
if(x<=3)
{
if(y<=3)
return 1;
if(y<=6)
return 2;
if(y<=9)
return 3;
}
if(x<=6)
{
if(y<=3)
return 4;
if(y<=6)
return 5;
if(y<=9)
return 6;
}
if(x<=9)
{
if(y<=3)
return 7;
if(y<=6)
return 8;
if(y<=9)
return 9;
}
}
int pd(int x,int y)
{
if(x==1||x==9||y==1||y==9)
return 6;
if(x==2||x==8||y==2||y==8)
return 7;
if(x==3||x==7||y==3||y==7)
return 8;
if(x==4||x==6||y==4||y==6)
return 9;
return 10;
}
void tj()
{
int all=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
all+=a[i][j]*pd(i,j);
ans=max(ans,all);
}
void dfs(int w)
{
if(w==82)
{
tj();
return;
}
int tx=w%9;
int ty=w/9+1;
if(!tx)
{
tx=9;ty--;
}
if(MAP[tx][ty])
dfs(w+1);
else
{
int g=fk(tx,ty);
for(int i=1;i<=9;i++)
if(!(x[tx]&(1<<i)))
if(!(y[ty]&(1<<i)))
if(!(k[g]&(1<<i)))
{
x[tx]+=(1<<i);
y[ty]+=(1<<i);
k[g]+=(1<<i);
a[tx][ty]=i;
dfs(w+1);
x[tx]-=(1<<i);
y[ty]-=(1<<i);
k[g]-=(1<<i);
}
}
//cout<<w<<endl;
}
int main()
{
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
{
scanf("%d",&MAP[i][j]);
a[i][j]=MAP[i][j];
if(MAP[i][j])
{
if((x[i]&(1<<MAP[i][j]))||(y[j]&(1<<MAP[i][j]))||(k[fk(i,j)]&(1<<MAP[i][j])))
{
puts("-1");
return 0;
}
x[i]|=(1<<MAP[i][j]);
y[j]|=(1<<MAP[i][j]);
k[fk(i,j)]|=(1<<MAP[i][j]);
}
}
dfs(1);
if(!ans)
puts("-1");
else
cout<<ans<<endl;
return 0;
}
tql
tql!