題見洛谷
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<cmath>#define LL long longusing 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);新聞熱點
疑難解答
