不知道为啥90(玄关)
查看原帖
不知道为啥90(玄关)
1069853
lijiayi11楼主2024/10/16 20:30
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
}p[85];
bool r[10][10],c[10][10],b[10][10];
int a[10][10],cntr[10],cntc[10],cntb[10],idx,ans=-1;
int f[10][10]={
	{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 id(int x,int y)
{
	return (x-1)/3*3+(y-1)/3+1;
}
bool cmp(node A,node B)
{
	if(cntr[A.x]!=cntr[B.x]);
	{
		return cntr[A.x]<cntr[B.x];
	}
	if(cntc[A.y]!=cntc[B.y])
	{
		return cntc[A.y]<cntc[B.y];
	}
	return cntb[id(A.x,A.y)]<cntb[id(B.x,B.y)];
}
void dfs(int cur)
{
	if(cur==idx+1)
	{
		int sum=0;
		for(int i=1;i<=9;i++)
		{
			for(int j=1;j<=9;j++)
			{
				sum+=a[i][j]*f[i][j];
			}
		}
		ans=max(ans,sum);
		return ;
	}
	int x=p[cur].x;
	int y=p[cur].y;
	for(int i=1;i<=9;i++)
	{
		if(!r[x][i] && !c[y][i] && !b[id(x,y)][i])
		{
			a[x][y]=i;
			r[x][i]=1;
			c[y][i]=1;
			b[id(x,y)][i]=1;
			dfs(cur+1);
			r[x][i]=0;
			c[y][i]=0;
			b[id(x,y)][i]=0;
			a[x][y]=0;
		}
	}
}
int main()
{
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			scanf("%d",&a[i][j]);
			//cin>>a[i][j];
			if(a[i][j])
			{
				r[i][a[i][j]]=1;
				c[j][a[i][j]]=1;
				b[id(i,j)][a[i][j]]=1;
			}
			else
			{
				p[++idx]={i,j};
				cntr[i]++;
				cntc[j]++;
				cntb[id(i,j)]++;
			}
		}
	}
	sort(p+1,p+idx+1,cmp);
	dfs(1);
	cout<<ans;
	return 0;
}
2024/10/16 20:30
加载中...