靶形数独80分求助
  • 板块学术版
  • 楼主dreamlzx
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/4/3 18:33
  • 上次更新2023/10/28 04:43:34
查看原帖
靶形数独80分求助
570251
dreamlzx楼主2022/4/3 18:33
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<iomanip>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
struct node{
	int x,y;
};
int a[10][10],x,n,used1[10][10],used2[10][10],used3[10][10],sum,ans=-1;
int db[10][10]={
	0,0,0,0,0,0,0,0,0,0,
	0,1,1,1,2,2,2,3,3,3,
	0,1,1,1,2,2,2,3,3,3,
	0,1,1,1,2,2,2,3,3,3,
	0,4,4,4,5,5,5,6,6,6,
	0,4,4,4,5,5,5,6,6,6,
	0,4,4,4,5,5,5,6,6,6,
	0,7,7,7,8,8,8,9,9,9,
	0,7,7,7,8,8,8,9,9,9,
	0,7,7,7,8,8,8,9,9,9,
} ;
int c[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,
};
void dfs(int x,int y){
	if(x==10){
		sum=0;
		for(int i=1;i<=9;i++){
			for(int j=1;j<=9;j++){
				sum+=a[i][j]*c[i][j];
			}
		}
		ans=max(ans,sum);
		return;
	}
	if(a[x][y])
	{
		if(y==9) dfs(x+1,1);
		else dfs(x,y+1);
		return;
	}
	for(int i=1;i<=9;i++){
		if(!used1[x][i]&&!used2[y][i]&&!used3[db[x][y]][i]){
			used1[x][i]=used2[y][i]=used3[db[x][y]][i]=1;
			a[x][y]=i;
			if(y==9)dfs(x+1,1);
			else dfs(x,y+1);
			used1[x][i]=used2[y][i]=used3[db[x][y]][i]=0;
			a[x][y]=0;
		}
	}
} 
int main(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			cin>>x;
			if(x==0){
				continue;
			}
			else{
				a[i][j]=x;
				used1[i][x]=used2[j][x]=used3[db[i][j]][x]=1;
			}
		}
	}
	dfs(1,1); 
	cout<<ans;
}
2022/4/3 18:33
加载中...