八皇后问题，只不过每一个点上加了一个权值，求一个权值最大的解。
以下是我的代码：
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int ans,r[8][8],d[8];
bool used1[8],used2[20],used3[20];
void dfs(int depth)
{
if(depth>=8)
{
int t(0);
for(int i=0;i<8;i++)
t+=r[i][d[i]];
ans=max(ans,t);
return;
}
for(int i=0;i<8;i++)
if(!used1[i] && !used2[depth+i] && !used3[8+depth-i-1])
{
d[depth]=i;
used1[i]=used2[depth+i]=used3[8+depth-i-1]=true;
dfs(depth+1);
used1[i]=used2[depth+i]=used3[8+depth-i-1]=false;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
int T;
scanf("%d",&T);
while(T--)
{
for(int i=0;i<8;i++)
for(int j=0;j<8;j++)
scanf("%d",&r[i][j]);
ans=0;
memset(d,0,8*sizeof(int));
memset(used1,false,8*sizeof(bool));
memset(used2,false,20*sizeof(bool));
memset(used3,false,20*sizeof(bool));
dfs(0);
printf("%5d\n",ans);
}
return 0;
}
posted on 2011-04-20 20:22
lee1r 阅读(218)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索