萌新求助TLE 75pts
查看原帖
萌新求助TLE 75pts
561529
Infinite_Energy楼主2023/8/1 19:31
#include<bits/stdc++.h>
using namespace std;
long long a[20][20],tot,ans=-1,score,num[100][5];
bool hang[20][20],lie[20][20],gong[20][20],vis[20][20],pd;
struct node{
	long long pos,sum;
}save[20];
bool cmp(node x,node y){
	return x.sum<y.sum;
}
long long calc1(long long x,long long y){
	if(x>=1&&x<=3&&y>=1&&y<=3){
		return 1;
	}
	if(x>=1&&x<=3&&y>=4&&y<=6){
		return 2;
	}
	if(x>=1&&x<=3&&y>=7&&y<=9){
		return 3;
	}
	if(x>=4&&x<=6&&y>=1&&y<=3){
		return 4;
	}
	if(x>=4&&x<=6&&y>=4&&y<=6){
		return 5;
	}
	if(x>=4&&x<=6&&y>=7&&y<=9){
		return 6;
	}
	if(x>=7&&x<=9&&y>=1&&y<=3){
		return 7;
	}
	if(x>=7&&x<=9&&y>=4&&y<=6){
		return 8;
	}
	if(x>=7&&x<=9&&y>=7&&y<=9){
		return 9;
	}
}
long long calc2(long long x,long long y){
	if(x==1||x==9||y==1||y==9){
		return 6;
	}
	if(x==2||x==8||y==2||y==8){
		return 7;
	}
	if(x==3||x==7||y==3||y==7){
		return 8;
	}
	if(x==4||x==6||y==4||y==6){
		return 9;
	}
	if(x==5&&y==5){
		return 10;
	}
}
void dfs(long long now,long long all){
	if(now==tot+1){
		ans=max(ans,all);
		return;
	}
	for(int x=1;x<=9;x++){
		if(hang[num[now][0]][x]==0&&lie[num[now][1]][x]==0&&gong[num[now][2]][x]==0){
			hang[num[now][0]][x]=1;
			lie[num[now][1]][x]=1;
			gong[num[now][2]][x]=1;
			dfs(now+1,all+num[now][3]*x);
			hang[num[now][0]][x]=0;
			lie[num[now][1]][x]=0;
			gong[num[now][2]][x]=0;
		}
	}
}
int main(){
	for(int i=1;i<=9;i++){
		save[i].pos=i;
	}
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			cin>>a[i][j];
			if(a[i][j]>0){
				hang[i][a[i][j]]=1;
				lie[j][a[i][j]]=1;
				gong[calc1(i,j)][a[i][j]]=1;
				score+=calc2(i,j)*a[i][j];
			}else{
				save[i].sum++;
			}
		}
	}
	sort(save+1,save+9+1,cmp);
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			if(a[save[i].pos][j]==0){
				tot++;
				num[tot][0]=save[i].pos;
				num[tot][1]=j;
				num[tot][2]=calc1(save[i].pos,j);
				num[tot][3]=calc2(save[i].pos,j);
			}
		}
	}
	dfs(0,score);
	cout<<ans<<endl;
	return 0;
}
2023/8/1 19:31
加载中...