#include<cstdio>
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}};
int r[10][10],ans(-1),tot(0);
bool squ[4][4][10],row[10][10],col[10][10];
void f(int i,int &x,int &y)
{
x=i/9+1;
y=i%9;
if(i%9==0)
{
x--;
y=9;
}
}
void g(int x,int y,int &xx,int &yy)
{
xx=x/3;
if(x%3)
xx++;
yy=y/3;
if(y%3)
yy++;
}
void dfs(const int &depth,const int &now)
{
tot++;
if(tot>=13000000)
return;
if(depth<=0)
{
if(ans<now)
ans=now;
return;
}
int x,y,xx,yy;
f(depth,x,y);
g(x,y,xx,yy);
if(r[x][y])
dfs(depth-1,now+r[x][y]*score[x][y]);
else
{
for(int i=1;i<=9;i++)
if(!squ[xx][yy][i] && !row[x][i] && !col[y][i])
{
squ[xx][yy][i]=row[x][i]=col[y][i]=true;
dfs(depth-1,now+i*score[x][y]);
squ[xx][yy][i]=row[x][i]=col[y][i]=false;
}
}
}
int main()
{
//*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
{
scanf("%d",&r[i][j]);
int xx,yy;
g(i,j,xx,yy);
squ[xx][yy][r[i][j]]=row[i][r[i][j]]=col[j][r[i][j]]=true;
}
dfs(81,0);
printf("%d\n",ans);
return 0;
}
posted on 2011-07-20 20:02
lee1r 閱讀(354)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索