记录编号	243916	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	1.577 s
提交时间	2016-03-30 21:46:10	内存使用	0.31 MiB

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<assert.h>
using std::max;
using std::cin;
using std::cout;
using std::endl;
const int MAXN=9+1,FULL=(1<<9)-1,getsc[][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},
};
int r[MAXN],c[MAXN],map[MAXN][MAXN],b[13],ans=-1,l=81;
inline int xy2b(int x,int y){
	return (x+3-1)/3+(y+3-1)/3*3;
}
inline void set(int x,int y,int k){
	r[x]|=(1<<k),c[y]|=(1<<k),b[xy2b(x,y)]|=(1<<k),map[x][y]=k;
}
inline void take(int x,int y,int k){
	r[x]&=~(1<<k),c[y]&=~(1<<k),b[xy2b(x,y)]&=~(1<<k),map[x][y]=0;
}
bool getpos(int& x,int &y,int& poss){
	bool flag=0;
	int n=10,cnt,now,t;
	for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) if(map[i][j]==0){
		t=now=r[i]|c[j]|b[xy2b(i,j)],cnt=0;
		/*if(now==FULL) {
			cout<<"无解";
			continue;
		}*/
		while(now) now&=(now-1),cnt++;
		cnt=(9-cnt);
		if(cnt<n) x=i,y=j,n=cnt,flag=1,poss=t;
		if(cnt==1) break;
	}
	if(flag) return true;
	else return false;//false for 没有可填位置(无解或满) 
}
/*void show(int x=0,int y=0){
	cout<<endl;
	for(int i=1;i<=9;i++,cout<<endl) for(int j=1;j<=9;j++) cout<<((i==x&&j==y)?"|":"")<<map[i][j]<<' ';
	cout<<endl;
}
int worksc(){
	int res=0;
	for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) res+=map[i][j]*getsc[i][j];
	return res;
}*/
void dfs(int s,int left){//当前分数s，剩下空白left
	if(s+left*9*10<ans)
		return;
	int x,y,poss;
	if(!getpos(x,y,poss)&&left==0) {
		if(left!=0) return;
		ans=max(ans,s);
		//printf("get");
		//show();
	}
	else{
		for(int i=9;i>=1;i--) if(((poss>>i)&1)==0) {
			set(x,y,i);//show(x,y);
			dfs(s+i*getsc[x][y],left-1),take(x,y,i);
		}
	}
}
int main(){
	freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout);
	int t,now=0;
	for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) {
		cin>>map[i][j];		
		if(map[i][j]) now+=map[i][j]*getsc[i][j],set(i,j,map[i][j]),l--;
	}
	dfs(now,l);
	/*for(int i=1;i<=9;i++,cout<<endl) for(int j=1;j<=9;j++) {
		int poss=r[i]&c[j]&b[xy2b(i,j)];
		for(int k=1;k<=9;k++) if((poss>>k)&1) cout<<k<<' ';
	}*/
	cout<<ans;
	//show();
}