蒟蒻求助 样例没过 自己看不出哪错了 球球大佬
查看原帖
蒟蒻求助 样例没过 自己看不出哪错了 球球大佬
573589
ande楼主2022/4/5 17:03
#include <bits/stdc++.h>
using namespace std;
const int N=15;
int score[11][11]= {
	{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}
};
typedef long long ll;
int ans = -1,sum;
int a[N][N];
int heng[N][N],z[N][N],s[5][N];
struct hh {
	int hang;
	int sum;
} sd[N];

bool cmp(hh a, hh b) {
	return a.sum<b.sum;
}

int qiuhe() {
	int sum=0;
	for(int i=1; i<=9; i++)
		for(int j=1; j<=9; j++) {
			sum+=a[i][j]*score[i][j];
		}/*cout<<endl;
	for(int i=1; i<=9; i++) {
			cout<<endl;
		for(int j=1; j<=9; j++) 
			printf("%d ",a[i][j]);}*/
	return sum;
}

void dfs(int dep,int x,int y) {
	if(dep == 10 ) {
		ans = max(qiuhe(),ans);
		return ;
	}
	if(y > 9) {//cout << dep <<" ";
		dfs(dep+1,sd[dep+1].hang,1);
		return ;
	}
	if(a[x][y] != 0) {
		dfs(dep,x,y+1);
		return ;
	} 
	else {
		for(int i=1; i<=9; i++) {
			
			if(heng[x][i] != 1 && z[y][i] != 1 && s[(x-1)/3*3+(y-1)/3+1][i] != 1) {
				heng[x][i] = z[y][i] = s[(x-1)/3*3+(y-1)/3+1][i] = 1;
				a[x][y] = i;
				dfs(dep,x,y+1);
				heng[x][i] = z[y][i] = s[(x-1)/3*3+(y-1)/3+1][i] = 0;
				a[x][y] = 0;
			}
			
		}
	}
	return ;
}


int main() {
	for(int i=1; i<=9; ++i) {
		
		for(int j=1; j<=9; ++j) {
			scanf("%d",&a[i][j]);
			if(a[i][j] == 0)
				sd[i].sum++;	
			heng[i][a[i][j]]=1;
			z[j][a[i][j]]=1;
		 	s[(i-1)/3*3+(j-1)/3+1][a[i][j]]=1;//biao ji
		}//cout<<sd[i].hang<<" ";
	}	
	for(int i=1;i<=9;i++)sd[i].hang = i;
	sort(sd+1,sd+10,cmp);
//cout<<sd[1].sum<<" "<<sd[2].sum;
	dfs(1,sd[1].hang,1);
/*for(int i=1;i<=9;i++){
	cout<<sd[i].hang<<" "<<sd[i].sum<<" "<<endl;
	}*/
		
	printf("%d",ans);
	return 0;      
}










2022/4/5 17:03
加载中...