国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > The Sultan's Successors UVA 167(八皇后问题)

The Sultan's Successors UVA 167(八皇后问题)

来源:程序员人生   发布时间:2014-10-06 08:00:01 阅读次数:3140次

说说:

其实这道题本质上就是一个八皇后问题。唯一的区别就是每个棋盘的格子都对应一个数字。最后要求输出,对应的解占据的格子的和的最大值。这只要在最后求出解的时候统计一下就可以了。下面就简单的说说八皇后问题,其实解法也不难。因为要求每行每列都要有棋子。因此只要确定每一行对应的棋子的列数就可以了。而对于每个棋子的所放的位置,同列上和对角线上不能有其他棋子,这个只要设一个访问数组保存一下就可以了。(注意要记得回溯)。至于对角线的表示方法,例如所在位置为(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 ; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生