RT.3 个关注

#include <bits/stdc++.h>
using namespace std;
namespace Main {
	int points[10][10];//(i,j) 分数
	int id[10][10];//(i,j)所属宫格
	int imap[10][10];//数独表
	bool vis_gongge[10][10];//第 i 个宫格 数字 j 是否出现过 
	bool vis_hang[10][10];//第i行，数字 j 是否出现过
	bool vis_lie[10][10];//第i列，数字 j 是否出现过 
	int ans;
	struct SX
	{
		int val,id;
		bool operator <(const SX& b)
		{
			return val<b.val;
		}
	}sx[10];
	void dfs(int ith,int j,int col) {
		int i=sx[ith].id;
		if(j==10) {
			dfs(ith+1,1,col);
			return;
		}
		if(ith==10) {
			ans=max(ans,col);
			return;
		}
		if(imap[i][j]) {
			if(vis_hang[i][imap[i][j]]||vis_lie[j][imap[i][j]]||vis_gongge[id[i][j]][imap[i][j]])return;
			vis_hang[i][imap[i][j]]=1;
			vis_lie[j][imap[i][j]]=1;
			vis_gongge[id[i][j]][imap[i][j]]=1;
			dfs(ith,j+1,col+imap[i][j]*points[i][j]);
			vis_hang[i][imap[i][j]]=0;
			vis_lie[j][imap[i][j]]=0;
			vis_gongge[id[i][j]][imap[i][j]]=0;
			return;
		}
		for(int num=1;num<=9;num++)
		{
			if(vis_hang[i][num]||vis_lie[j][num]||vis_gongge[id[i][j]][num])continue;
			vis_hang[i][num]=1;
			vis_lie[j][num]=1;
			vis_gongge[id[i][j]][num]=1;
			imap[i][j]=num;
			dfs(ith,j+1,col+num*points[i][j]);
			imap[i][j]=0;
			vis_hang[i][num]=0;
			vis_lie[j][num]=0;
			vis_gongge[id[i][j]][num]=0;
		}
	}
	void init(int idx,int l,int r,int _point) {
		if(idx==10)return;
		if(idx==5) {
			points[5][5]=_point;
			init(idx+1,l-1,r+1,_point-1);
			return;
		}
		if(idx<5) {
			for(int i=l; i<=r; i++) {
				points[idx][i]=_point;
			}
			init(idx+1,l+1,r-1,_point+1);
		}
		if(idx>5) {
			for(int i=l; i<=r; i++) {
				points[idx][i]=_point;
			}
			init(idx+1,l-1,r+1,_point-1);
		}
	}
	void init2(int idx,int l,int r,int _point) {
		if(idx==10)return;
		if(idx==5) {
			points[5][5]=_point;
			init2(idx+1,l-1,r+1,_point-1);
			return;
		}
		if(idx<5) {
			for(int i=l; i<=r; i++) {
				points[i][idx]=_point;
			}
			init2(idx+1,l+1,r-1,_point+1);
		}
		if(idx>5) {
			for(int i=l; i<=r; i++) {
				points[i][idx]=_point;
			}
			init2(idx+1,l-1,r+1,_point-1);
		}
	}
	void init3() {
		for(int i=1; i<=9; i++) {
			for(int j=1; j<=9; j++) {
				int h=(i-1)/3+1;
				int l=(j-1)/3+1;
				id[i][j]=(h-1)*3+l;
			}
		}
	}
	void main() {
		
		init(1,1,9,6);
		init2(1,1,9,6);
		init3();
		for(int i=1; i<=9; i++) {
			for(int j=1; j<=9; j++) {
				scanf("%d",&imap[i][j]);
				sx[i].val+=(imap[i][j]==0);
			}
			sx[i].id=i;
		}
		sort(sx+1,sx+10);
		dfs(1,1,0);
		if(!ans)
		{
			printf("-1\n");
			return;
		}
		printf("%d",ans);
	}
}
int main() {
	Main::main();
	return 0;
}