题目
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #define LL long long using namespace std; int lief[10][10],hangf[10][10],gef[10][10]; int quan[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 ge[10][10]= { 0,0,0,0,0,0,0,0,0,0, 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, }; int a[10][10]; int sum=0,sum2; void dfs(int x,int y,int tot) { if(x==10&&y==1){ sum=max(sum,tot); return; } if(a[x][y]){ if(y<9) dfs(x,y+1,tot); else dfs(x+1,1,tot); } else{ for(int i=1;i<=9;i++){ if( !lief[y][i] && !hangf[x][i]&& !gef[ge[x][y]][i]) { lief[y][i]=1,hangf[x][i]=1,gef[ge[x][y]][i]=1,a[x][y]=i; if(y<9) dfs(x,y+1,tot+i*quan[x][y]); else dfs(x+1,1,tot+i*quan[x][y]); lief[y][i]=0,hangf[x][i]=0,gef[ge[x][y]][i]=0,a[x][y]=0; } } } } int main() { for(int i=1;i<=9;i++) for(int j=1;j<=9;j++){ scanf("%d",&a[i][j]); sum+=quan[i][j]*a[i][j]; lief[j][a[i][j]]=1; hangf[i][a[i][j]]=1; gef[ge[i][j]][a[i][j]]=1; } sum2=sum; dfs(1,1,sum); if(sum2==sum) printf("-1"); else printf("%d",sum); return 0; }