靶状数组题目链接 90分，而且超时很严重，与或运算不会23333333
#include <cstdio> #include <iostream> using namespace std; int s[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 g[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 f1[10][10],f2[10][10],f3[10][10],t[10][10],tot=-1;//若木有答案输出-1 void dfs(int x,int y,int ans) { if(x==1&&y==10)//终止条件 { tot=max(ans,tot); return; } if(t[x][y]!=0)//之前有数已填入 { if(x+1<=9) dfs(x+1,y,ans+s[x][y]*t[x][y]);//向右走 else dfs(1,y+1,ans+s[x][y]*t[x][y]);//去向下一行 } else//无数 { int k=g[x][y]; for(int i=1;i<=9;i++) { if(f1[x][i]==0&&f2[y][i]==0&&f3[k][i]==0) { f1[x][i]=1; f2[y][i]=1; f3[k][i]=1; if(x+1<=9) dfs(x+1,y,ans+s[x][y]*i); else dfs(1,y+1,ans+s[x][y]*i);//同上 f1[x][i]=0; f2[y][i]=0; f3[k][i]=0; } } } } int main() { int i,j; for(i=1;i<=9;i++) for(j=1;j<=9;j++) { scanf("%d",&t[i][j]); int x=t[i][j]; f1[i][x]=1; f2[j][x]=1; int k=g[i][j]; f3[k][x]=1;//先标记上 } dfs(1,1,0); printf("%d",tot); }方法2（正解）： 我们在搜索过程中用一个数组叫vin[i][j]来表示i,j这个位置能填数的方案有几种 这样我们从方案数少的开始搜索，就可以减少递归次数，防止超时
#include <cstdio> #include <iostream> #include <cstring> using namespace std; int s[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 w[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 hang[10][10],lie[10][10],quyu[10][10]; int a[10][10]; int n; int maxans=-1; int vin[10][10]; void dfs(int t) { if(t>n) { int maxf=0; for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) if(!a[i][j]) return; else maxf+=a[i][j]*s[i][j]; maxans=max(maxans,maxf); return; } memset(vin,0,sizeof(vin)); int x1,y1; int min1=1e8; for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) if(!a[i][j]) { for(int k=1;k<=9;k++) if(!hang[i][k]&&!lie[j][k]&&!quyu[w[i][j]][k]) vin[i][j]++; if(min1>vin[i][j]) { x1=i; y1=j; min1=vin[i][j]; } if(min1==1) break; } if(min1==0) return; if(min1==1e8) { int maxf=0; for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) if(!a[i][j]) return; else maxf+=a[i][j]*s[i][j]; maxans=max(maxans,maxf); return; } for(int k=1;k<=9;k++) if(!hang[x1][k]&&!lie[y1][k]&&!quyu[w[x1][y1]][k]) { a[x1][y1]=k; hang[x1][k]=1; lie[y1][k]=1; quyu[w[x1][y1]][k]=1; dfs(t+1); a[x1][y1]=0; hang[x1][k]=0; lie[y1][k]=0; quyu[w[x1][y1]][k]=0; } } int main() { for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) { scanf("%d",&a[i][j]); if(a[i][j]) { hang[i][a[i][j]]=1; lie[j][a[i][j]]=1; quyu[w[i][j]][a[i][j]]=1; } else n++; } dfs(1); printf("%d",maxans); return 0; }