P1074 靶状数独(优化)

2/10/2017来源:ASP.NET技巧人气:748

题见洛谷

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #define LL long long using namespace std; bool lief[10][10],hangf[10][10],gef[10][10]; int ans=-1,can[10][10],n=0,a[10][10];//can[][]用来记此点能放几种数 int quan[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 ge[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, }; bool flag(int x,int y,int k) { if(!gef[ge[x][y]][k]&&!hangf[x][k]&&!lief[y][k]) return true; return false; } void dfs(int k) { if(k>n) { int tot=0; for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) if(!a[i][j]) return; else tot+=a[i][j]*quan[i][j]; ans=max(ans,tot); return; } else { int minn=99999999,nx,ny; memset(can,0,sizeof(can)); for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) if(!a[i][j]) { for(int x=1;x<=9;x++) if(flag(i,j,x)) can[i][j]++; if(minn>can[i][j]) { minn=can[i][j]; nx=i;ny=j;//找到最小can的,先来填 } if(minn==1)break; } if(minn==0)return;//无解 if(minn==99999999) { int tot=0; for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) if(!a[i][j]) return; else tot+=a[i][j]*quan[i][j]; ans=max(ans,tot); return; } for(int i=1;i<=9;i++) if(flag(nx,ny,i)) { hangf[nx][i]=true; lief[ny][i]=true; gef[ge[nx][ny]][i]=true; a[nx][ny]=i; dfs(k+1); hangf[nx][i]=false; lief[ny][i]=false; gef[ge[nx][ny]][i]=false; a[nx][ny]=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])n++; else { lief[j][a[i][j]]=true; hangf[i][a[i][j]]=true; gef[ge[i][j]][a[i][j]]=true; } } dfs(1); PRintf("%d",ans); return 0; }