80分求助
查看原帖
80分求助
764850
zy_oier楼主2023/8/3 15:27
#include<bits/stdc++.h>
using namespace std;
int a[101][101]={};
int k[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 maxx=0,s=0;
bool f1[101][101]={},f2[101][101]={},f3[101][101]={};
void dfs(int x,int y,int ans){
    if (y>9){dfs(x+1,1,ans);return;}
    if (x>9){maxx=max(maxx,ans);return;}
    if (a[x][y]>0) {dfs(x,y+1,ans+a[x][y]*k[x][y]);return;}
    else{
	    for(int i=1;i<=9;i++)if(f1[x][i]==0&&f2[y][i]==0&&f3[(x-1)/3*3+(y-1)/3+1][i]==0){
		    f1[x][i]=1;f2[y][i]=1;f3[(x-1)/3*3+(y-1)/3+1][i]=1;
		    dfs(x,y+1,ans+i*k[x][y]);
		    f1[x][i]=0;f2[y][i]=0;f3[(x-1)/3*3+(y-1)/3+1][i]=0;
		}
	} 
}
int main(){
    for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)scanf("%d",&a[i][j]);
    for (int i=1;i<=9;i++)for (int j=1;j<=9;j++)if (a[i][j]!=0){
		f1[i][a[i][j]]=1;
		f2[j][a[i][j]]=1;
		f3[(i-1)/3*3+(j-1)/3+1][a[i][j]]=1;
		s=s+a[i][j]*k[i][j];
	}
	dfs(1,1,0); 
	printf("%d",maxx==0?-1:maxx);
	return 0;
} 
2023/8/3 15:27
加载中...