求条(全部输出-1)
查看原帖
求条(全部输出-1)
1234324
god_std楼主2025/6/16 19:48
//god_std 2025.6.13 21:28
//P1074 PC 80pts
#include<bits/stdc++.h>
#define int long long
#define n 9
using namespace std;
int tube[11][11];
int block[11][11];
int q1[101];
int q2[101];
int a[11][11];
int visrow[11][11];
int viscol[11][11];
int visblo[11][11];
int comeu[11][11];
int rowcnt[101];
int colcnt[101];
int ans=-1,it,total;
void dfs(int x,int y,int u)
{
	if(u>it)
	{
		int num=total;
		for(int i=1;i<=it;i++)
		{
			int x=q1[i],y=q2[i];
			num+=a[x][y]*tube[x][y];
		}
		ans=max(num,ans);
		return ;
	}
	for(int i=1;i<=9;i++)
	{
		int g=block[x][y];
		if(visrow[x][i]==0&&viscol[y][i]==0&&visblo[g][i]==0)
		{
			a[x][y]=i;
			visrow[x][i]=1;
			viscol[y][i]=1;
			visblo[g][i]=1;
			rowcnt[x]++;
			colcnt[y]++;
			int maxr,maxc;
			maxr=maxc=-1;
			for(int j=1;j<=9;j++)
			{
				if(rowcnt[j]>maxr&&rowcnt[j]<9)
					maxr=j;
			} 
			for(int j=1;j<=9;j++)
			{
				if(colcnt[j]>maxc&&colcnt[j]<9)
					maxc=j;
			} 
			dfs(maxr,maxc,comeu[maxr][maxc]);
			a[x][y]=0; 
			visrow[x][i]=0;
			viscol[y][i]=0;
			visblo[g][i]=0;
			rowcnt[x]--;
			colcnt[y]--;
		}
	}
	return ;
}
signed main()
{
//	freopen("soduku0.in","r",stdin);
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			tube[i][j]=10-max(abs(i-5),abs(j-5));
			block[i][j]=(i-1)/3+1+3*((j-1)/3+1)-3;
		}
	}
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			cin>>a[i][j];
			if(a[i][j]==0)
				it++,
				q1[it]=i,
				q2[it]=j,
				comeu[i][j]=it;
			else
				rowcnt[i]++,
				colcnt[j]++,
				visrow[i][a[i][j]]=1,
				viscol[j][a[i][j]]=1,
				total+=tube[i][j]*a[i][j],
				visblo[block[i][j]][a[i][j]]=1;
		}
	}
	dfs(q1[1],q2[1],1);
	cout<<ans;
	return 0;
} 
2025/6/16 19:48
加载中...