超时两个点90分,马蜂良好,求调
查看原帖
超时两个点90分,马蜂良好,求调
1492684
pengbaoqing楼主2025/7/26 10:59
#include<bits/stdc++.h>
using namespace std;
struct tr{
	int x,y,z,s;
}c[90];
/*bool cmp(tr a,tr b){
	return a.s<b.s;
}*/
int h[12][12],l[12][12],b[12][12];//行,列,小九宫格中i是否出现过
int a[12][12],u=0,v[12][12];//a为数,t为可填个数,v为基数
int ans=-1;
void bj(){
	int sum=0;
	for(int t=1;t<=9;t++){
		for(int i=1;i<=9;i++){
			sum+=a[t][i]*v[t][i]; 
		}
	}
	if(sum>ans) ans=sum;
}
void dfs(int de){
	if(de>u){
		bj();
		return ;
	}
	int x=c[de].x;
	int y=c[de].y;
	int z=c[de].z;
	for(int t=1;t<=9;t++){
		if(h[x][t]==0&&l[y][t]==0&&b[z][t]==0){
			h[x][t]=1;
			l[y][t]=1;
			b[z][t]=1;
			a[x][y]=t;
			dfs(de+1);
			h[x][t]=0;
			l[y][t]=0;
			b[z][t]=0;
			a[x][y]=0;
		}
	}
}
void sorr(){
	tr o;
	for(int t=1;t<=u;t++){
		int k=t;
		for(int i=t;i<=u;i++){
			if(c[i].s<c[k].s) k=i;
		}
		if(k!=t){
			o=c[k];
			c[k]=c[t];
			c[t]=o;
		}
	}
}
int main(){
	for(int t=1;t<=9;t++){
		for(int i=1;i<=9;i++){
			if(abs(t-5)>abs(i-5)) v[t][i]=10-abs(t-5);
			else v[t][i]=10-abs(i-5);
		}
	}
	for(int t=1;t<=9;t++){
		for(int i=1;i<=9;i++){
			scanf("%d",&a[t][i]);
			h[t][a[t][i]]=1;
			l[i][a[t][i]]=1;
			b[(t-1)/3*3+(i-1)/3+1][a[t][i]]=1;
		    if(a[t][i]==0){
		    	u++;
		    	c[u].x=t;
		    	c[u].y=i;
		    	c[u].z=(t-1)/3*3+(i-1)/3+1;
			}
		}
	}
	for(int t=1;t<=u;t++){
		int x=c[t].x,y=c[t].y,z=c[t].z;
		for(int i=1;i<=9;i++){
			if(h[x][i]==0&&l[y][i]==0&&b[z][i]==0) c[t].s+=1;
		}
	}
	//sort(c+1,c+u+1,cmp);
	sorr();
	dfs(1);
	cout<<ans;
	return 0;
} 
2025/7/26 10:59
加载中...