| 记录编号 |
333589 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[NOIP 2009]靶形数独 |
最终得分 |
100 |
| 用户昵称 |
 AntiLeaf |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
7.060 s |
| 提交时间 |
2016-10-31 06:24:56 |
内存使用 |
0.28 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int w[15][15]={{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}
},
id[15][15]={{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}
},n=9;
void dfs1(int,int);
void dfs2(int,int);
int a[15][15],cnt[15]={0},tmp=0,ans=-1;
bool visa[15][15]={{false}},visb[15][15]={{false}},visc[15][15]={{false}};//行，列，块
int main(){
#define MINE
#ifdef MINE
freopen("sudoku.in","r",stdin);
freopen("sudoku.out","w",stdout);
#endif
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
if(a[i][j]){
visa[i][a[i][j]]=visb[j][a[i][j]]=visc[id[i][j]][a[i][j]]=true;
//cnt[id[i][j]]++;
}
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(!a[i][j])
for(int k=1;k<=n;k++)if(!visa[i][k]&&!visb[j][k]&&!visc[id[i][j]][k])cnt[id[i][j]]++;
if(a[1][1]==1)dfs1(1,1);
else dfs2(n,n);
printf("%d",ans);
#ifndef MINE
printf("\n-------------------------DONE-------------------------\n");
for(;;);
#endif
return 0;
}
inline void dfs1(int x,int y){
if(y>n){
x++;
y=1;
}
//printf("dfs(%d,%d,%d)\n",x,y,tmp);
if(x==n+1){
ans=max(ans,tmp);
return;
}
if(tmp+(n-x)*720+(n-y+1)*72<=ans)return;
if(a[x][y]){
tmp+=w[x][y]*a[x][y];
dfs1(x,y+1);
tmp-=w[x][y]*a[x][y];
}
for(int i=9;i;i--)if(!visa[x][i]&&!visb[y][i]&&!visc[id[x][y]][i]){
visa[x][i]=visb[y][i]=visc[id[x][y]][i]=true;
tmp+=w[x][y]*i;
dfs1(x,y+1);
tmp-=w[x][y]*i;
visa[x][i]=visb[y][i]=visc[id[x][y]][i]=false;
}
}
inline void dfs2(int x,int y){
if(!y){
x--;
y=n;
}
//printf("dfs(%d,%d,%d)\n",x,y,tmp);
if(!x){
ans=max(ans,tmp);
return;
}
if(tmp+(x-1)*720+y*72<=ans)return;
if(a[x][y]){
tmp+=w[x][y]*a[x][y];
dfs2(x,y-1);
tmp-=w[x][y]*a[x][y];
}
for(int i=1;i<=n;i++)if(!visa[x][i]&&!visb[y][i]&&!visc[id[x][y]][i]){
visa[x][i]=visb[y][i]=visc[id[x][y]][i]=true;
tmp+=w[x][y]*i;
dfs2(x,y-1);
tmp-=w[x][y]*i;
visa[x][i]=visb[y][i]=visc[id[x][y]][i]=false;
}
}
/*
0 0 0 0 0 6 0 0 3
0 0 0 0 0 0 6 0 0
0 0 0 0 0 3 0 0 0
0 0 0 1 0 0 2 0 0
0 0 0 0 3 0 0 0 4
0 2 7 0 0 0 0 3 0
1 0 0 0 6 8 4 7 9
0 9 6 2 7 0 1 0 5
8 0 0 0 9 0 3 0 0
Answer:
2864
*/
/*
1 0 0 0 5 0 0 9 3
0 0 0 9 1 2 0 0 0
0 0 0 6 0 4 0 0 0
8 6 0 0 0 0 0 0 0
0 0 0 0 6 0 0 0 7
0 0 0 0 0 0 0 0 0
0 0 0 0 4 0 7 0 2
4 2 0 3 8 0 0 0 9
0 0 0 0 0 9 0 3 4
Answer:
2852
*/