P1074 靶形数独（TLE 75）

2019-11-14 09:33:53

字体：大中小

来源：转载

供稿：网友

题目

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<cmath>#define LL long longusing namespace std;int lief[10][10],hangf[10][10],gef[10][10];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,};int a[10][10];int sum=0,sum2;void dfs(int x,int y,int tot){ if(x==10&&y==1){ sum=max(sum,tot); return; } if(a[x][y]){ if(y<9) dfs(x,y+1,tot); else dfs(x+1,1,tot); } else{ for(int i=1;i<=9;i++){ if( !lief[y][i] && !hangf[x][i]&& !gef[ge[x][y]][i]) { lief[y][i]=1,hangf[x][i]=1,gef[ge[x][y]][i]=1,a[x][y]=i; if(y<9) dfs(x,y+1,tot+i*quan[x][y]); else dfs(x+1,1,tot+i*quan[x][y]); lief[y][i]=0,hangf[x][i]=0,gef[ge[x][y]][i]=0,a[x][y]=0; } } }}int main(){ for(int i=1;i<=9;i++) for(int j=1;j<=9;j++){ scanf("%d",&a[i][j]); sum+=quan[i][j]*a[i][j]; lief[j][a[i][j]]=1; hangf[i][a[i][j]]=1; gef[ge[i][j]][a[i][j]]=1; } sum2=sum; dfs(1,1,sum); if(sum2==sum) PRintf("-1"); else printf("%d",sum); return 0; }

上一篇：347. Top K Frequent Elements

下一篇：代码整洁之道（一）