记录编号	332766	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	11.660 s
提交时间	2016-10-29 09:39:50	内存使用	0.29 MiB

#include "stdio.h"
#include "string.h"
#include "math.h"
#include "time.h"
#include "algorithm"
using namespace std;

const int score[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},
};
const int pos[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 G[15][15], ans;
bool line[15][15], cross[15][15], block[15][15];
// line[i][j]: 第i列中数字j是否出现过   cross[]行   block[]九宫格

inline bool Check(const int& x, const int& y, const int& num)
{
	if (line[y][num]) return 0;
	if (cross[x][num]) return 0;
	if (block[pos[x][y]][num]) return 0;
	line[y][num] = cross[x][num] = block[pos[x][y]][num] = 1;
	return 1;
}

void DFS(const int& x, const int& y, const int& tot)
{
	// printf("x:%d y:%d tot:%d\n", x, y, tot);
	// printf("\n");
	// for (int i = 1; i <= 9; ++i) {
	// 	for (int j = 1; j <= 9; ++j)
	// 		printf("%d ", G[i][j]);
	// 	printf("\n");
	// }
	// if ((double)clock() / CLOCKS_PER_SEC >= 4.9) return;
	if (y == 0) {
		ans = max(ans, tot);
		return;
	}
	if (G[x][y]) {
		if (x == 1) DFS(9, y - 1, tot + G[x][y] * score[x][y]);
		else DFS(x - 1, y, tot + G[x][y] * score[x][y]);
	}
	else {
		for (int i = 1; i <= 9; ++i) {
			G[x][y] = i;
			if (Check(x, y, i)) {
				if (x == 1) DFS(9, y - 1, tot + G[x][y] * score[x][y]);
				else DFS(x - 1, y, tot + G[x][y] * score[x][y]);
				line[y][i] = cross[x][i] = block[pos[x][y]][i] = 0;
			}
			G[x][y] = 0;
			// line[y][i] = cross[x][i] = block[pos[x][y]][i] = 0;
		}
	}
}

#define SUBMIT
int main(int argc, char const *argv[])
{
#ifdef SUBMIT
	freopen("sudoku.in", "r", stdin); freopen("sudoku.out", "w", stdout);
#endif

	for (int i = 1; i <= 9; ++i)
		for (int j = 1; j <= 9; ++j) {
			scanf("%d", &G[i][j]);
			if (G[i][j]) Check(i, j, G[i][j]);
		}

	DFS(9, 9, 0);

	if (!ans) printf("-1\n");
	else printf("%d\n", ans);

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif

	return 0;
}