洛谷P1074求助
查看原帖
洛谷P1074求助
1037979
23456wl楼主2024/8/14 15:04
#include<bits/stdc++.h>
using namespace std;
int s[20][20],ss[9][20]={
{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}};
long long max_ans=-1,ans;
bool r[20][20],c[20][20],g[20][20];
void dfs(int x,int y){
	if(s[x][y]>0){
		if(x==9&&y==9){
			ans=0;
			for(int i=1;i<=9;i++){
				for(int j=1;j<=9;j++){
					ans+=s[i][j]*ss[i-1][j-1];
				}
			}
			max_ans=max(ans,max_ans);
		}else if(y==9)dfs(x+1,1);
		else dfs(x,y+1);
	}else{
		for(int i=1;i<=9;i++){
			if(!r[x][i]&&!c[y][i]&&!g[(x-1)/3*3+(y-1)/3+1][i]){
				s[x][y]=i;r[x][i]=1;c[y][i]=1;
				g[(x-1)/3*3+(y-1)/3+1][i]=1;
				if(x==9&&y==9){
					ans=0;
					for(int i=1;i<=9;i++){
						for(int j=1;j<=9;j++){
							ans+=s[i][j]*ss[i-1][j-1];
						}
					}
					max_ans=max(ans,max_ans);
				}else if(y==9)dfs(x+1,1);
				else dfs(x,y+1);
				s[x][y]=0;r[x][i]=0;c[y][i]=0;
				g[(x-1)/3*3+(y-1)/3+1][i]=0;
			}
		}
	}
}
int main(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			scanf("%d",&s[i][j]);
			if(s[i][j]>0){
				r[i][s[i][j]]=1;
				c[j][s[i][j]]=1;
				g[(i-1)/3*3+(j-1)/3+1][s[i][j]]=1;
			}
		}
	}
	dfs(1,1);
	printf("%lld",max_ans);
	return 0;
}

各位大佬能帮我看看吗 QAQ 不知为何只有85分

2024/8/14 15:04
加载中...