卡不动了,一直TLE两个点
查看原帖
卡不动了,一直TLE两个点
983702
lrj3247楼主2025/1/15 16:53
#include<iostream>
#include<algorithm>
using namespace std;
inline int read(){
	int w = 0 , f = 1;
	char ch = getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch = getchar();
	}
	while('0'<=ch&&ch<='9'){
		w=w*10+(ch-'0');
		ch = getchar();
	}
	return w*f;
}
void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
const int N = 15;
struct Point{
	int x,y,xz;
}s[N*N];
inline bool cmp(Point X,Point Y){
//	if(X.x==Y.x) return X.y<Y.y;
	return X.xz<Y.xz;
}
int a[N][N],ans,sum,tot;//ans表示目前最高分数 ,sum为当前总分 。 
int f[9][9]={
	{6,6,6,6,6,6,6,6,6},
	{6,7,7,7,7,7,7,7,6},
	{6,7,8,8,8,8,8,7,6},
	{6,7,8,9,9,9,8,7,6},
	{6,7,8,9,10,9,8,7,6},
	{6,7,8,9,9,9,8,7,6},
	{6,7,8,8,8,8,8,7,6},
	{6,7,7,7,7,7,7,7,6},
	{6,6,6,6,6,6,6,6,6}
};
int g[9][9]={
	{1,1,1,2,2,2,3,3,3},
	{1,1,1,2,2,2,3,3,3},
	{1,1,1,2,2,2,3,3,3},
	{4,4,4,5,5,5,6,6,6},
	{4,4,4,5,5,5,6,6,6},
	{4,4,4,5,5,5,6,6,6},
	{7,7,7,8,8,8,9,9,9},
	{7,7,7,8,8,8,9,9,9},
	{7,7,7,8,8,8,9,9,9},
};
bool vis1[N][N],vis2[N][N],vis3[N][N];//vis1[i][j]为第i行,数字j是否被用过,vis2[i][j]表示第i列,数字j是否被用过 ,vis3[i][j]表示第i个九宫格,数字j是否被用过
bool flag;//表示这个数独是否被填满过。 
void dfs(int step){//当前为第x行,第y列 
	if(step>tot){
		flag=true;
		ans = max(ans,sum);
		return ;
	}
	int x = s[step].x,y=s[step].y;
	for(int i = 1 ; i<=9 ; i++){
		int now = g[x-1][y-1];
		if(!vis1[x][i]&&!vis2[y][i]&&!vis3[now][i]){
			vis1[x][i]=vis2[y][i]=vis3[now][i]=true;
			sum+=f[x-1][y-1]*i;
			dfs(step+1);
			vis1[x][i]=vis2[y][i]=vis3[now][i]=false;
			sum-=f[x-1][y-1]*i;
		}
	}
	return ;
}
int main(){
	for(int i = 1 ; i<=9 ; i++){
		for(int j = 1 ; j<=9 ; j++){
			a[i][j]=read();
			if(a[i][j]!=0){
				vis1[i][a[i][j]]=true;
				vis2[j][a[i][j]]=true;
				int now = g[i-1][j-1];
				vis3[now][a[i][j]]=true;
				sum+=f[i-1][j-1]*a[i][j];
			}
		}
	}
	tot = 0;
	for(int i = 1 ; i<=9 ; i++){
		for(int j = 1 ; j<=9 ; j++){
			if(a[i][j]==0){
				++tot;
				s[tot]={i,j,9};
				int now = g[i-1][j-1];
				for(int z = 1 ; z<=9 ; z++){
					if(vis1[i][z]||vis2[j][z]||vis3[now][z]){
						--s[tot].xz;
					}
				}
			}
		}
	}
	sort(s+1,s+tot+1,cmp);
	dfs(1);
	if(!flag) putchar('-'),putchar('1');
	else write(ans);
	return 0;
}
2025/1/15 16:53
加载中...