比赛 20200109 评测结果 WAAAAAAAAAAAAAAATAAA
题目名称 靶形数独 最终得分 90
用户昵称 数声风笛ovo 运行时间 4.948 s
代码语言 C++ 内存使用 9.56 MiB
提交时间 2020-01-09 20:40:15
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int ans=-123456789,a[10][10],b[10][10],c[10][10];
bool f1[10][10],f2[10][10],f3[10][10];
void dfs(int step){
  int i,j,k,s,xx,yy,zz=10;
  for(i=1;i<=9;i++)
    for(j=1;j<=9;j++)if(a[i][j]==0){
        for(s=0,k=1;k<=9;k++){
        	if(!f1[c[i][j]][k]&&!f2[i][k]&&!f3[j][k]){
        		s++;
        	}
        }
        if(s<zz){
        	zz=s; xx=i; yy=j;
        } 
    }
  	if(zz==10){
      	for(k=0,i=1;i<=9;i++){
      		for(j=1;j<=9;j++){
      			k+=a[i][j]*b[i][j];
      		}
         		 
      	}
    ans=max(ans,k);
    return;
	}
  	if(zz==0)return;
  	for(k=1;k<=9;k++){
  		if(!f1[c[xx][yy]][k] && !f2[xx][k] && !f3[yy][k]){
        	a[xx][yy]=k;
        	f1[c[xx][yy]][k]=f2[xx][k]=f3[yy][k]=1;
			dfs(step+1);
       	 	a[xx][yy]=0;
			f1[c[xx][yy]][k]=f2[xx][k]=f3[yy][k]=0; 
      	}
  	}
   	return ; 	
}
int qwq(){
	freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout); 
	int i,j,k;
    for(i=1;i<=9;i++){
    	for(j=1;j<=9;j++){
    		scanf("%d",&a[i][j]);
       	 	b[i][j]=10-max(abs(i-5),abs(j-5));
       	 	c[i][j]=(i-1)/3*3+(j-1)/3+1;
        	f1[c[i][j]][a[i][j]]=1;
	    	f2[i][a[i][j]]=1;
	    	f3[j][a[i][j]]=1;
    	}	
	}
    dfs(1);
    printf("%d\n",ans);
    return 0;
}
int ovo=qwq();
int main(){;}