记录编号	600586	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	407.[NOIP 2009]靶形数独	最终得分	100
用户昵称	对立猫猫对立	是否通过	通过
代码语言	C++	运行时间	1.450 s
提交时间	2025-05-07 21:41:27	内存使用	3.49 MiB

#include <bits/stdc++.h>
using namespace std;
int a[10][10], dx[10][10], dy[10][10], dz[30][10], Max = -1;
int get(int x, int y) {
	return (x - 1) / 3 * 10 + (y - 1) / 3;
}
int score[20][20] = {
	{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 tem = 10, x, y;
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			if (a[i][j])continue;
			int s = 0;
			for (int k = 1; k <= 9; k++) {
				if (dx[i][k] | dy[j][k] | dz[get(i, j)][k])continue;
				s++;
			}
			if (s < tem) {
				tem = s;
				x = i;
				y = j;
			}
		}
	}
	if (tem == 10) {
		int ans = 0;
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				ans += score[i][j] * a[i][j];
			}
		}
		Max = max(Max, ans);
		return ;
	}
	for (int i = 1; i <= 9; i++) {
		if (dx[x][i] | dy[y][i] | dz[get(x, y)][i])continue;
		dx[x][i] = 1;
		dy[y][i] = 1;
		dz[get(x, y)][i] = 1;
		a[x][y] = i;
		dfs();
		dx[x][i] = 0;
		dy[y][i] = 0;
		dz[get(x, y)][i] = 0;
		a[x][y] = 0;
	}
}
int main() {
//	freopen("sudoku.in", "r", stdin);
//	freopen("sudoku.out", "w", stdout);
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			scanf("%d", &a[i][j]);
			dx[i][a[i][j]] = 1;
			dy[j][a[i][j]] = 1;
			dz[get(i, j)][a[i][j]] = 1;
		}
	}
	dfs();
	printf("%d", Max);
	return 0;
}