题解
2023-03-04 17:50:10
发布于：上海
#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){
//debug();
//cout<<x<<" "<<y<<endl;
//cout<<abcd<<endl;
if(abcd==10){
//debug();
ans=max(ans,cnt);
return ;
}
if(arr[x][y]!=0){
if(y==9){
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+i*value[x][y]);
abcd--;
}else{
dfs(x,y+1,cnt+i*value[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;
//cout<<cntzero[i].cnt<<" ";
}
//cout<<endl;
sort(cntzero+1,cntzero+10,cmp);
dfs(cntzero[abcd].idx,1,cnt);
if(ans==0) cout<<-1;
else cout<<ans;
return 0;
}
全部评论 8
#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){
//debug();
//cout<<x<<" "<<y<<endl;
//cout<<abcd<<endl;
if(abcd==10){//debug(); 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(y9){
abcd++;dfs(cntzero[abcd].idx,1,cnt+i*value[x][y]); abcd--; }else{ dfs(x,y+1,cnt+i*value[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; //cout<<cntzero[i].cnt<<" ";}
//cout<<endl;
sort(cntzero+1,cntzero+10,cmp);
dfs(cntzero[abcd].idx,1,cnt);
if(ans==0) cout<<-1;
else cout<<ans;return 0;
}2024-10-11 来自 甘肃
0
有帮助，赞一个