记录编号	277266	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.118 s
提交时间	2016-07-05 09:54:58	内存使用	0.29 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;

int block_index[10][10] = {{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 value[10][10] = {{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}
};

int map[10][10];
int pos[101][2];       ////zeros
bool line[10][10], row[10][10], block[10][10];  //vis
int res = -1;
int times;

void dfs(int zeros, int sum)
{
	if(!zeros)
	{
		if(sum > res)res = sum;
		return;
	}
	if(sum + zeros * 9 * 9 < res)return;
	if(times++ > 8000000)return;
	int i = pos[zeros][0], j = pos[zeros][1];
	for(int k = 1; k <= 9; k++)  //place number
	{
		if(!line[i][k] && !row[j][k] && !block[block_index[i][j]][k])
		{
			line[i][k] = row[j][k] = block[block_index[i][j]][k] = true;
			dfs(zeros - 1, sum + k * value[i][j]);
			line[i][k] = row[j][k] = block[block_index[i][j]][k] = false;
		}
	}
}

int main()
{
	freopen("sudoku.in", "r", stdin);
	freopen("sudoku.out", "w", stdout);
	int tot = 0;
	int zeros = 0;
	for(int i = 1; i <= 9; i++)
	{
		for(int j = 1; j < 10; j++)
		{
			int vvv;
			scanf("%d", &vvv);
			if(map[i][j] = vvv)
			{
				line[i][vvv] = row[j][vvv] = block[block_index[i][j]][vvv] = 1;
				tot += vvv * value[i][j];
			}else
			{
				zeros++;
				pos[zeros][0] = i;
				pos[zeros][1] = j;
			}
		}
	}
	dfs(zeros, tot);
	printf("%d\n", res? res: -1);
	return 0;
}