记录编号	128508	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.908 s
提交时间	2014-10-17 20:12:59	内存使用	0.29 MiB

#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <vector>
#include <queue>

#define maxn ((int)1e5 + 4)
#if defined DEBUG
FILE *in = fopen("test", "r");
#define out stdout
#else
FILE *in = fopen("sudoku.in", "r");
FILE *out = fopen("sudoku.out", "w");
#endif
using namespace std;
inline void getint(int &x){
	char c = fgetc(in);
	while(!isdigit(c)) c = fgetc(in);
	x = c - '0';
	while(isdigit(c = fgetc(in)))x = x * 10 - '0' + c;
}

/*===========================================*/
#define lowbit(x) (x & -x)
#define gs(x, y) (x / 3 * 3 + y / 3)
#define f(a) (bitcnt(RNG &~(row[a.x] | col[a.y] | squ[gs(a.x,a.y)])))
const int RNG = 1022/*状态的范围*/,val[9][9] = {
	{6,6,6,6,6,6,6,6,6},
	{6,7,7,7,7,7,7,7,6},
	{6,7,8,8,8,8,8,7,6},
	{6,7,8,9,9,9,8,7,6},
	{6,7,8,9,10,9,8,7,6},
	{6,7,8,9,9,9,8,7,6},
	{6,7,8,8,8,8,8,7,6},
	{6,7,7,7,7,7,7,7,6},
	{6,6,6,6,6,6,6,6,6}};
struct P{
	int x, y;
	P(){}
}blank[80];
int bcnt = 0, ord[80];
int row[9] = {0}, col[9] = {0}, squ[9] = {0};//状态
int ans = 0;
bool known = 0;
inline int bitcnt(int x){
	int a = 0;
	while(x){
		if(x & 1)++a;
		x >>= 1;
	}
	return a;
}
inline void init(){
	int i, j, k, t;
	for(i = 0;i < 9;++i)for(j = 0;j < 9;++j){
		getint(k);
		if(k){
			t = 1 << k;
			row[i] ^= t, col[j] ^= t, squ[gs(i,j)] ^= t;
			ans += k * val[i][j];
		}
		else{
			ord[bcnt] = bcnt;
			blank[bcnt].x = i;
			blank[bcnt++].y = j;
		}
	}
}
inline void dfs(int cur, int now){
	if(cur == bcnt){
		if(now > ans)ans = now,known = 1;
		return;
	}
	int mincnt = 10, min_it, i, t;
	for(i = cur;i < bcnt;++i)
		if((t = f(blank[ord[i]])) < mincnt)
			mincnt = t, min_it = i;
	P x = blank[ord[min_it]];
	if(cur!=min_it)ord[cur] ^= ord[min_it] ^= ord[cur] ^= ord[min_it];
	int bits = RNG &~(row[x.x] | col[x.y] | squ[gs(x.x,x.y)]);
	while(bits){
		t = lowbit(bits); bits ^= t;
		i = bitcnt(t - 1);
		row[x.x] ^= t, col[x.y] ^= t, squ[gs(x.x,x.y)] ^= t;
		dfs(cur + 1, now + i * val[x.x][x.y]);
		row[x.x] ^= t, col[x.y] ^= t, squ[gs(x.x,x.y)] ^= t;
	}
}
int main(){
	init();
	dfs(0, ans);
	if(known)
		fprintf(out, "%d\n", ans);
	else fprintf(out, "-1\n");
	return 0;
}