tijei
2024-08-23 20:10:08
发布于:天津
#include<bits/stdc++.h>
using namespace std;
int arr[15][15];
bool hang[10][10],lie[10][10],gong[10][10][10];
struct stu{
int cnt,idx;
};
stu cntzero[15];
int value[11][11]={
0,0,0,0,0,0,0,0,0,0,0,
0,6,6,6,6,6,6,6,6,6,0,
0,6,7,7,7,7,7,7,7,6,0,
0,6,7,8,8,8,8,8,7,6,0,
0,6,7,8,9,9,9,8,7,6,0,
0,6,7,8,9,10,9,8,7,6,0,
0,6,7,8,9,9,9,8,7,6,0,
0,6,7,8,8,8,8,8,7,6,0,
0,6,7,7,7,7,7,7,7,6,0,
0,6,6,6,6,6,6,6,6,6,0,
0,0,0,0,0,0,0,0,0,0,0
};
int dx[9]={1,1,1,0,0,0,-1,-1,-1};
int dy[9]={0,-1,1,0,-1,1,0,-1,1};
int abcd=1;
void debug(){
cout<<endl;
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
}
bool check(int x,int y,int key){
if(hang[x][key]||lie[y][key])return false;
int a=(x-1)/3,b=(y-1)/3;
if(gong[a][b][key]) return false;
return true;
}
long long ans=0;
void dfs(int x,int y,long long cnt){
if(abcd10){
ans=max(ans,cnt);
return ;
}
if(arr[x][y]!=0){
if(y9){
abcd++;
dfs(cntzero[abcd].idx,1,cnt);
abcd--;
}else{
dfs(x,y+1,cnt);
}
}else{
for(int i=1;i<=9;i++){
if(!check(x,y,i)) continue;
arr[x][y]=i;
hang[x][i]=1;
lie[y][i]=1;
int a=(x-1)/3,b=(y-1)/3;
gong[a][b][i]=1;
if(y==9){
abcd++;
dfs(cntzero[abcd].idx,1,cnt+ivalue[x][y]);
abcd--;
}else{
dfs(x,y+1,cnt+ivalue[x][y]);
}
hang[x][i]=0;
lie[y][i]=0;
int c=(x-1)/3,d=(y-1)/3;
gong[c][d][i]=0;
arr[x][y]=0;
}
}
}
bool cmp(stu a,stu b){
return a.cnt<b.cnt;
}
int main(){
int cnt=0;
for(int i=1;i<=9;i++){
int z=0;
for(int j=1;j<=9;j++){
cin>>arr[i][j];
cnt+=arr[i][j]*value[i][j];
if(arr[i][j]0){
z++;
continue;
}
hang[i][arr[i][j]]=1;
lie[j][arr[i][j]]=1;
gong[(i-1)/3][(j-1)/3][arr[i][j]]=1;
}
cntzero[i].cnt=z;
cntzero[i].idx=i;
}
sort(cntzero+1,cntzero+10,cmp);
dfs(cntzero[abcd].idx,1,cnt);
if(ans0) cout<<-1;
else cout<<ans;
return 0;
}
这里空空如也
有帮助,赞一个