大佬求助,写了三天了样例都过不了
查看原帖
大佬求助,写了三天了样例都过不了
111349
bobzbh楼主2022/8/4 21:32
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
bool use[4][11][11];//1 minisq,2 x,3 y
int plate[11][11],score[11][11],maxx=0,rn=0,zero=0;
struct node
{
	int ze,sq,x,y;
}s[81];
bool cmp(node a,node b)
{
	if(a.ze!=b.ze)
	{
		return a.ze<b.ze;
	}
	else
	{
		if(a.y!=b.y)
		{
			return a.y<b.y;
		}
		else
		{
			return a.x<b.x;
		}
	}
}
int minisq(int x,int y)
{
	if(x>=1&&x<=3)
	{
		if(y>=1&&y<=3)
		{
			return 1;
		}
		if(y>=4&&y<=6)
		{
			return 4;
		}
		if(y>=7&&y<=9)
		{
			return 7;
		}
	}
	if(x>=4&&x<=6)
	{
		if(y>=1&&y<=3)
		{
			return 2;
		}
		if(y>=4&&y<=6)
		{
			return 5;
		}
		if(y>=7&&y<=9)
		{
			return 8;
		}
	}
	if(x>=7&&x<=9)
	{
		if(y>=1&&y<=3)
		{
			return 3;
		}
		if(y>=4&&y<=6)
		{
			return 6;
		}
		if(y>=7&&y<=9)
		{
			return 9;
		}
	}
}
void dfs(int pla,int sum)
{
	if(pla>zero)
	{
		if(sum>maxx)
		{
			maxx=sum;
		}
		return ;
	}
	bool number[10];
	for(int i=1; i<=9; ++i)
	{
		if(use[1][minisq(s[pla].x,s[pla].y)][i]==1||use[2][s[pla].x][i]==1||use[3][s[pla].y][i]==1)
		{
			number[i]=1;
		}
		else
		{
			number[i]=0;
		}
	}
	for(int i=1; i<=9; ++i)
	{
		if(number[i]==0)
		{
			use[1][minisq(s[pla].x,s[pla].y)][i]=1;
			use[2][s[pla].x][i]=1;
			use[3][s[pla].y][i]=1;
			dfs(pla+1,sum+i*score[s[pla].x][s[pla].y]);
			use[1][minisq(s[pla].x,s[pla].y)][i]=0;
			use[2][s[pla].x][i]=0;
			use[3][s[pla].y][i]=0;
		}
	}
	return ;
}
int main()
{
	memset(use,0,sizeof(use));
	for(int i=1; i<=9; ++i)
	{
		int sum=0;
		int pl=zero+1;
		for(int j=1; j<=9; ++j)
		{
			cin>>plate[i][j];
			if(plate[i][j]==0)
			{
				zero++;
				sum++;
				s[zero].x=j;
				s[zero].y=i;
				s[zero].sq=minisq(j,i);
			}
			else
			{
				use[1][minisq(j,i)][plate[i][j]]=1;
			}
		}
		for(int j=pl; j<=zero; ++j)
		{
			s[j].ze=sum;
		}
	}
	sort(s+1,s+zero+1,cmp);
	for(int i=1; i<=5; ++i)
	{
		for(int j=i; j<=10-i; ++j)
		{
			for(int k=i; k<=10-i; ++k)
			{
				score[j][k]=5+i;
			}
		}
	}
	dfs(1,0);
	cout<<maxx; 
	return 0;
}
2022/8/4 21:32
加载中...