靶形数独

#include<bits/stdc++.h>
using namespace std;
int arr[15][15];
bool hang[10][10],lie[10][10],gong[10][10][10];
struct stu {
	int cnt,idx;
};
stu cntzero[15];
int value[11][11]= {
	0,0,0,0,0,0,0,0,0,0,0,
	0,6,6,6,6,6,6,6,6,6,0,
	0,6,7,7,7,7,7,7,7,6,0,
	0,6,7,8,8,8,8,8,7,6,0,
	0,6,7,8,9,9,9,8,7,6,0,
	0,6,7,8,9,10,9,8,7,6,0,
	0,6,7,8,9,9,9,8,7,6,0,
	0,6,7,8,8,8,8,8,7,6,0,
	0,6,7,7,7,7,7,7,7,6,0,
	0,6,6,6,6,6,6,6,6,6,0,
	0,0,0,0,0,0,0,0,0,0,0
};
int dx[9]= {1,1,1,0,0,0,-1,-1,-1};
int dy[9]= {0,-1,1,0,-1,1,0,-1,1};
int abcd=1;
void debug() {
	cout<<endl;
	for(int i=1; i<=9; i++) {
		for(int j=1; j<=9; j++) {
			cout<<arr[i][j]<<" ";
		}
		cout<<endl;
	}
}
bool check(int x,int y,int key) {
	if(hang[x][key]||lie[y][key]) {
		return false;
	}
	int a=(x-1)/3,b=(y-1)/3;
	if(gong[a][b][key]) {
		return false;
	}
	return true;
}
long long ans=0;
void dfs(int x,int y,long long cnt) {
	if(abcd==10) {
		ans=max(ans,cnt);
		return;
	}
	if(arr[x][y]!=0) {
		if(y==9) {
			abcd++;
			dfs(cntzero[abcd].idx,1,cnt);
			abcd--;
		} else {
			dfs(x,y+1,cnt);
		}
	} else {
		for(int i=1; i<=9; i++) {
			if(!check(x,y,i)) {
				continue;
			}
			arr[x][y]=i;
			hang[x][i]=1;
			lie[y][i]=1;
			int a=(x-1)/3,b=(y-1)/3;
			gong[a][b][i]=1;
			if(y==9) {
				abcd++;
				dfs(cntzero[abcd].idx,1,cnt+i*value[x][y]);
				abcd--;
			} else {

				dfs(x,y+1,cnt+i*value[x][y]);

			}
			hang[x][i]=0;
			lie[y][i]=0;
			int c=(x-1)/3,d=(y-1)/3;
			gong[c][d][i]=0;
			arr[x][y]=0;
		}
	}
}
bool cmp(stu a,stu b) {
	return a.cnt<b.cnt;
}
int main() {
	int cnt=0;
	for(int i=1; i<=9; i++) {
		int z=0;
		for(int j=1; j<=9; j++) {
			cin>>arr[i][j];
			cnt+=arr[i][j]*value[i][j];
			if(arr[i][j]==0) {
				z++;
				continue;
			}
			hang[i][arr[i][j]]=1;
			lie[j][arr[i][j]]=1;
			gong[(i-1)/3][(j-1)/3][arr[i][j]]=1;

		}
		cntzero[i].cnt=z;
		cntzero[i].idx=i;
	}
	sort(cntzero+1,cntzero+10,cmp);
	dfs(cntzero[abcd].idx,1,cnt);
	if(ans==0) {
		cout<<-1;
	} else {
		cout<<ans;
	}
	return 0;
}