dfs 优化搜索顺序
我们可以想到一种方法，每次找可以填的数最少的格子进行dfs。
离线 85pts
在线 100pts
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct data{int x,y;}; const int maxn=100; //由于未知原因，我的代码需要开10倍的数组不然会RE（？？？） int ans=-1,val[maxn][maxn],score[maxn][maxn],l[maxn],r[maxn]; //val,score:填入的数，和给出的分数 l,r:该行/列已填几个数 bool use1[maxn][maxn],use2[maxn][maxn],use3[10][10][maxn],vis[maxn][maxn]; //use1,2,3:行、列、九宫格限制可填的数 inline int blo(int &a) {return (a-1)/3+1;} //求所在块的编号 inline data find(){ //在线找可填数最小的点 int mxl=-1,mxr=-1,L,R; for(int i=1;i<=9;++i) if(l[i]>mxl&&l[i]<9) L=i,mxl=l[i]; for(int i=1;i<=9;++i) if(r[i]>mxr&&!val[L][i]) R=i,mxr=r[i]; return (data){L,R}; } inline void dfs(int step,int tot,data node){ if(step==81) {ans=ans>tot ? ans:tot; return ;} int x=node.x,y=node.y; for(int i=1;i<=9;++i){ if(use1[x][i]||use2[y][i]||use3[blo(x)][blo(y)][i]) continue; val[x][y]=i; ++l[x]; ++r[y]; use1[x][i]=1; use2[y][i]=1; use3[blo(x)][blo(y)][i]=1; dfs(step+1,tot+i*score[x][y],find()); val[x][y]=0; --l[x]; --r[y]; use1[x][i]=0; use2[y][i]=0; use3[blo(x)][blo(y)][i]=0; //回溯 } } int main(){ int tot=0,cnt=0; for(int i=1;i<=9;++i) for(int j=1;j<=9;++j){ scanf("%d",&val[i][j]); if(!val[i][j]) continue; ++cnt; ++l[i]; ++r[j]; use1[i][val[i][j]]=1; use2[j][val[i][j]]=1; use3[blo(i)][blo(j)][val[i][j]]=1; } for(int i=5;i>=1;--i){ int x1=i,x2=10-i,x3=i,x4=10-i; int y1=i,y2=i,y3=10-i,y4=10-i; for(int j=10-i;j>=i;--j){ score[x1][y1]=i+5; score[x2][y2]=i+5; score[x3][y3]=i+5; score[x4][y4]=i+5; if(val[x1][y1]&&!vis[x1][y1]) tot+=val[x1][y1]*score[x1][y1],vis[x1][y1]=1; if(val[x2][y2]&&!vis[x2][y2]) tot+=val[x2][y2]*score[x2][y2],vis[x2][y2]=1; if(val[x3][y3]&&!vis[x3][y3]) tot+=val[x3][y3]*score[x3][y3],vis[x3][y3]=1; if(val[x4][y4]&&!vis[x4][y4]) tot+=val[x4][y4]*score[x4][y4],vis[x4][y4]=1; ++x1; ++y2; --y3; --x4; } //按照题意给出分数 } dfs(cnt,tot,find()); printf("%d",ans); return 0; }