原题链接
75分存档待改
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<queue> #include<stdio.h> using namespace std; struct hehe { int xp,yp; }empt[100]; int sma[10][10],x[10][10],y[10][10],a[10][10],ans=-1,an,emp; int q[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 h[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, }; void dfs(int maki,int tot) { int k; int nx=empt[tot].xp,ny=empt[tot].yp; if(tot==emp+1) { ans=max(ans,maki); return; } for(k=1;k<=9;k++) if((x[nx][k]==0)&&(y[ny][k]==0)&&(sma[h[nx][ny]][k]==0)) { a[nx][ny]=k; x[nx][k]=1; y[ny][k]=1; sma[h[nx][ny]][k]=1; tot++; dfs(maki+k*q[nx][ny],tot); a[nx][ny]=0; x[nx][k]=0; y[ny][k]=0; sma[h[nx][ny]][k]=0; tot--; } } int main() { int i,j; for(i=1;i<=9;i++) for(j=1;j<=9;j++) { scanf("%d",&a[i][j]); if(a[i][j]!=0) { x[i][a[i][j]]=1; y[j][a[i][j]]=1; sma[h[i][j]][a[i][j]]=1; an+=a[i][j]*q[i][j]; } else { emp++; empt[emp].xp=i; empt[emp].yp=j; } } dfs(an,1); printf("%d",ans); return 0; }修改后已AC AC代码
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<queue> #include<stdio.h> using namespace std; int sma[10][10],x[10][10],y[10][10],a[10][10],can[10][10],ans=-1,emp; int q[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 h[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, }; void dfs(int tot) { int i,j,k,nx,ny,sum=0,mi=99999999; if(tot>emp) { for(i=1;i<=9;i++) for(j=1;j<=9;j++) if(a[i][j]==0) return; else sum+=a[i][j]*q[i][j]; ans=max(ans,sum); } memset(can,0,sizeof(can)); for(i=1;i<=9;i++) for(j=1;j<=9;j++) if(!a[i][j]) { for(k=1;k<=9;k++) if((!x[i][k])&&(!y[j][k])&&(!sma[h[i][j]][k])) can[i][j]++; if(can[i][j]<mi) { mi=can[i][j]; nx=i; ny=j; } if(mi==1) break; } if(mi==0) return; if(mi==99999999) { int ma=0; for(i=1;i<=9;i++) for(j=1;j<=9;j++) if(a[i][j]==0) return; else ma+=a[i][j]*q[i][j]; ans=max(ma,ans); return; } for(k=1;k<=9;k++) if((!x[nx][k])&&(!y[ny][k])&&(!sma[h[nx][ny]][k])) { a[nx][ny]=k; x[nx][k]=1; y[ny][k]=1; sma[h[nx][ny]][k]=1; dfs(tot+1); a[nx][ny]=0; x[nx][k]=0; y[ny][k]=0; sma[h[nx][ny]][k]=0; } } int main() { int i,j; for(i=1;i<=9;i++) for(j=1;j<=9;j++) { scanf("%d",&a[i][j]); if(a[i][j]!=0) { x[i][a[i][j]]=1; y[j][a[i][j]]=1; sma[h[i][j]][a[i][j]]=1; } else emp++; } dfs(1); printf("%d",ans); return 0; }