The Sultan's Successors UVA 167（八皇后问题）
来源：程序员人生 发布时间：2014-10-06 08:00:01 阅读次数：3149次
说说：
其实这道题本质上就是一个八皇后问题。唯一的区别就是每个棋盘的格子都对应一个数字。最后要求输出，对应的解占据的格子的和的最大值。这只要在最后求出解的时候统计一下就可以了。下面就简单的说说八皇后问题，其实解法也不难。因为要求每行每列都要有棋子。因此只要确定每一行对应的棋子的列数就可以了。而对于每个棋子的所放的位置，同列上和对角线上不能有其他棋子，这个只要设一个访问数组保存一下就可以了。（注意要记得回溯）。至于对角线的表示方法，例如所在位置为（x，y），那么一条对角线可以用x+y表示，另一条对角线可以用x-y表示，但是由于数组的下标非负，因此可以将第二条对角线的值设为x-y+7，这样就可以用一个二维数组来表示，一个相应的位置上能不能放棋子啦。具体的分析，请参见刘汝佳的《算法竞赛入门经典》P123
八皇后问题。
源代码：
#include <stdio.h>
#include <string.h>
char vis[3][17];
int c[9];//存放每行的棋子所在的列数
int val[9][9];
int max,num=0;
void search(int);
int main(){
int k,i,j;
// freopen("data","r",stdin);
scanf("%d",&k);
while(k--){
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
scanf("%d",&val[i][j]);
memset(vis,0,sizeof(vis));
max=0;
search(1);
printf("%5d
",max);
}
return 0;
}
void search(int cur){
int i,sum;
if(cur>8){
sum=0;
for(i=1;i<=8;i++)
sum+=val[i][c[i]];
num++;
max=sum>max?sum:max;
}
else
for(i=1;i<=8;i++)
if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+7]){//同列，同对角线都没有其他棋子
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+7]=1;
c[cur]=i;
search(cur+1);
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+7]=0;//注意回溯
}
return ;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
