试题 算法提高 8皇后·改
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。
输入格式
一个8*8的棋盘。
输出格式
所能得到的最大数字和
样例输入
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
样例输出
260
数据规模和约定
棋盘上的数字范围0~99
解题思路：在八皇后问题的算法的基础上加一个最大值判断：遍历八皇后排列的每一种可能，并取八皇后所在格子数字和的最大值。
AC代码如下：
#include <iostream>
#include <cmath>
using namespace std;
int queenPos[10];
int G[10][10];
int maxV=0;
void NQueen(int k){
//在0-k-1行皇后已经摆好的情况下，摆低k行及其后的皇后
int i;
if(k==8){
int thisV=0;
for( i=0;i<8;i++){
// cout<<queenPos[i]+1<<" ";
thisV+=G[i][queenPos[i]];
}
// cout<<endl;
maxV=max(maxV,thisV);
return;
}
for(int i=0;i<8;i++){//第i列
int j;
for(j=0;j<k;j++){//j行
if(queenPos[j]==i || abs(queenPos[j]-i)==abs(k-j) )
break;
//冲突则测试下一个
}
if(j==k){//当前选的位置i不冲突
queenPos[k]=i;
//将第k个皇后摆放在位置i
NQueen(k+1);
}
}
}
int main(int argc, char** argv) {
for(int i=0;i<8;i++){
for(int j=0;j<8;j++)
cin>>G[i][j];
}
NQueen(0);
cout<<maxV<<endl;
return 0;
}