90TLE求助
查看原帖
90TLE求助
285617
黑影洞人楼主2022/10/28 21:02
#include<cstdio>
#include<algorithm>
#define N 10
using namespace std;
int a[N][N],tot,ans,res;
int bx[N*N],by[N*N],nxt,hyf;
int zer[N];
struct ptn{
	int x,y;
}b[N*N];
int v[N][N]={
	{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 tx[N][N]={
	{0,0,0,0,0,0,0,0,0,0},
	{0,1,1,1,1,1,1,1,1,1},
	{0,1,1,1,1,1,1,1,1,1},
	{0,1,1,1,1,1,1,1,1,1},
	{0,4,4,4,4,4,4,4,4,4},
	{0,4,4,4,4,4,4,4,4,4},
	{0,4,4,4,4,4,4,4,4,4},
	{0,7,7,7,7,7,7,7,7,7},
	{0,7,7,7,7,7,7,7,7,7},
	{0,7,7,7,7,7,7,7,7,7},
};
bool cmp(ptn a,ptn b){
	return zer[a.x]<zer[b.x];
}
bool check(int x,int y){
	int cnt1[10]={0},cnt2[10]={0},cnt3[10]={0};
	for(int i=1;i<=9;i++)if(a[i][y]&&(++cnt1[a[i][y]])>=2)return 0;
	for(int i=1;i<=9;i++)if(a[x][i]&&(++cnt2[a[x][i]])>=2)return 0;
	int sx=tx[x][y],sy=tx[y][x];
	for(int i=sx;i<=sx+2;i++){
		for(int j=sy;j<=sy+2;j++){
			if(a[i][j]&&(++cnt3[a[i][j]])>=2)return 0;
		}
	}
	return 1;
}
void dfs(int q){
	if(!check(b[q].x,b[q].y))return;
	if(q>=nxt){
		ans=max(ans,res);
		return;
	}
	int xx=b[q+1].x,yy=b[q+1].y;
	for(int j=9;j>=1;j--){
		a[xx][yy]=j;
		tot++;
		res+=v[xx][yy]*j;
		dfs(q+1);
		tot--;
		res-=v[xx][yy]*j;
		a[xx][yy]=0;
	}
}
signed main(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			scanf("%d",&a[i][j]);
			if(a[i][j])tot++,res+=v[i][j]*a[i][j];
			if(!a[i][j])b[++nxt]=(ptn){i,j},zer[i]++;
		}
	}
	sort(b+1,b+nxt+1,cmp);
	dfs(0);
	if(ans==0)puts("-1");
	else printf("%d",ans);
	return 0;
}

2022/10/28 21:02
加载中...