并不会剪枝的萌新求助
查看原帖
并不会剪枝的萌新求助
6677
Pinkie_Pie楼主2020/8/14 15:05

一直改一直T,枯了都

#include<iostream>
#include<cstdio>
using namespace std;
int map[9][9];
int heng[9][9];
int zong[9][9];
int gz[9][9];
int maxn=-1;
int point=0;
int ans=0;
int max(int aa,int bb)
{
	if(aa>=bb)	return aa;
	return bb;
}
int ll=0;
void dfs(int a,int b,int c)
{
	if(c==ll)
	{
		ans++;
		point=map[4][4]*10;
		for(int i=0;i<8;i++)
		{
			point+=map[0][i]*6;
			point+=map[i][8]*6;
			point+=map[8][8-i]*6;
			point+=map[8-i][0]*6;
		}
		for(int i=0;i<6;i++)
		{
			point+=map[1][i+1]*7;
			point+=map[i+1][7]*7;
			point+=map[7][7-i]*7;
			point+=map[7-i][1]*7;
		}
		for(int i=0;i<4;i++)
		{
			point+=map[2][i+2]*8;
			point+=map[i+2][6]*8;
			point+=map[6][6-i]*8;
			point+=map[6-i][2]*8;
		}
		point+=map[3][3]*9;
		point+=map[3][4]*9;
		point+=map[3][5]*9;
		point+=map[4][3]*9;
		point+=map[4][5]*9;
		point+=map[5][3]*9;
		point+=map[5][4]*9;
		point+=map[5][5]*9;
		maxn=max(maxn,point);
		return;
//		for(int i=0;i<9;i++)
//		{
//			for(int j=0;j<9;j++)
//			{
//				cout<<map[i][j]<<' ';
//			}
//			cout<<endl;
//		}
//		cout<<endl;
	}
	if(map[a][b]==0)
	{
		for(int i=0;i<9;i++)
		{
			if(heng[i][a]==1 || zong[i][b]==1 || gz[i][b/3+(3*(a/3)+1)]==1)
				continue;
			map[a][b]=i+1;
			heng[i][a]=1;
			zong[i][b]=1;
			gz[i][b/3+(3*(a/3)+1)]=1;
			dfs((a+((b+1)/9))%9,(b+1)%9,c+1);
			map[a][b]=0;
			heng[i][a]=0;
			zong[i][b]=0;
			gz[i][b/3+(3*(a/3)+1)]=0;
		}
	}
	else
	{
		dfs((a+((b+1)/9))%9,(b+1)%9,c);
	}
	return;
}
int min(int aa,int bb)
{
	if(aa>=bb) return bb;
	return aa;
}
int tx,ty,ta;
int minm=11;
int main()
{
	for(int i=0;i<=9;i++)
	{
		for(int j=0;j<9;j++)
		{
			heng[i][j]=0;
			zong[i][j]=0;
			gz[i][j]=0;
		}
	}
	for(int i=0;i<9;i++)
	{
		ta=0;
		for(int j=0;j<9;j++)
		{
			scanf("%d",&map[i][j]);
			if(map[i][j]!=0)
			{
				heng[map[i][j]-1][i]=1;
				zong[map[i][j]-1][j]=1;
				gz[map[i][j]-1][j/3+(3*(i/3)+1)]=1;
			}
			else if(map[i][j]==0)
			{
				ta++;
				ll++;
			}
		}
		if(ta<minm)
			tx=i;
		minm=min(minm,ta);
	}
	minm=2147483647;
	for(int i=0;i<9;i++)
	{
		ta=0;
		for(int j=0;j<9;j++)
		{
			if(map[j][i]==0)
			{
				ta++;
			}
		}
		if(ta<minm)
			ty=i;
		minm=min(minm,ta);
	}
	dfs(tx,0,0);
	if(ans==0)
	{
		printf("-1\n");
		return 0;
	}
	printf("%d\n",maxn);
}

剪不动了QAQ

2020/8/14 15:05
加载中...