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

什么 蓝题能用dfs做DFS大法好这道题就是一道数独的加强版还要算分数数独问题就是DFS回溯加剪枝优化。填数独那就是dfs枚举填数情况剪枝加回溯解出来时 再去乘以图表就行了#includebits/stdc.h using namespace std; long long n0,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 x0; for(int i9;i1;i--) { if(h[nn][i]falsel[m][i]falseg[(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.zb.z; } void dfs(long long m) { for(int im;in;i) { s[i].zf(s[i].x,s[i].y); } sort(sm,sn1,cmp); long long xs[m].x,ys[m].y; if(cnt90*(n-m1)ans) return; if(mn1) { ansmax(ans,cnt); return ; } if(f(x,y)0) return; for(int i9;i1;i--) { if(h[x][i]falsel[y][i]falseg[(x-1)/3][(y-1)/3][i]false) { a[x][y]i; h[x][i]true; l[y][i]true; cnti*c[x][y]; g[(x-1)/3][(y-1)/3][i]true; dfs(m1); 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 i1;i9;i) { for(int j1;j9;j) { cina[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; cnta[i][j]*c[i][j]; }else{ n; s[n].xi; s[n].yj; s[n].z0; } } } dfs(1); coutans; return 0; }