洛谷P1074 [NOIP 2009 提高组] 靶形数独题解

什么 蓝题能用dfs做？！

DFS大法好！

这道题就是一道数独的加强版，还要算分数，数独问题就是DFS回溯加剪枝优化。

填数独

那就是dfs枚举填数情况（剪枝加回溯）

解出来时 再去乘以图表就行了

#include<bits/stdc++.h> using namespace std; long long n=0,cnt,a[10][10],ans=-1,c[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 }; bool h[10][10],l[10][10],g[4][4][10]; long long f (long long nn,long long m) { long long x=0; for(int i=9;i>=1;i--) { if(h[nn][i]==false&&l[m][i]==false&&g[(nn-1)/3][(m-1)/3][i]==false) x++; } return x; } struct ccs { long long x,y,z; }s[82]; bool cmp(ccs a,ccs b) { return a.z<b.z; } void dfs(long long m) { for(int i=m;i<=n;i++) { s[i].z=f(s[i].x,s[i].y); } sort(s+m,s+n+1,cmp); long long x=s[m].x,y=s[m].y; if(cnt+90*(n-m+1)<=ans) return; if(m==n+1) { ans=max(ans,cnt); return ; } if(f(x,y)==0) return; for(int i=9;i>=1;i--) { if(h[x][i]==false&&l[y][i]==false&&g[(x-1)/3][(y-1)/3][i]==false) { a[x][y]=i; h[x][i]=true; l[y][i]=true; cnt+=i*c[x][y]; g[(x-1)/3][(y-1)/3][i]=true; dfs(m+1); cnt-=i*c[x][y]; a[x][y]=0; h[x][i]=false; l[y][i]=false; g[(x-1)/3][(y-1)/3][i]=false; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) { cin>>a[i][j]; if(a[i][j]!=0) { h[i][a[i][j]]=true; l[j][a[i][j]]=true; g[(i-1)/3][(j-1)/3][a[i][j]]=true; cnt+=a[i][j]*c[i][j]; }else{ n++; s[n].x=i; s[n].y=j; s[n].z=0; } } } dfs(1); cout<<ans; return 0; }