问题描述 :

规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。

输入说明 :

一个8*8的棋盘。

数据规模和约定

　　棋盘上的数字范围0~99

输出说明 :

所能得到的最大数字和

AC代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int a[9][9];
int q[9];//关键点 因为依据题意 一行只能摆放一个棋子 所以数组下标存储皇后的行 数组元素存储皇后的列
int max(int n1, int n2)
 {
	if (n1 > n2)
        return n1;
	return n2;
}
bool judge(int k)
{
    for(int i=1;i<k;i++)//每次只要看新放置的一列 与前面几列比较 看有无不合格的放置
    {
    if(abs(i-k)==abs(q[i]-q[k])||q[i]==q[k])//关键点 当列的差等于横的差 在同一斜线上 用绝对值看以求两个方向
    {
        return 0;
    }
    }
    return 1;
}
int mmax=0;
int tmp=-1;//不定义成0 更为保险
void dfs(int k)
{
    if(k==9)
    {
        tmp=max(tmp,mmax);
        return;

    }
    for(int i=1;i<9;i++)
    {
        q[k]=i;
        if(judge(k))
        {
            mmax+=a[k][i];

            dfs(k+1);
            mmax-=a[k][i];//注意返回时要剪掉加上的
        }

    }

}
int main()
{
    for (int i=1;i<9;i++)
    {
        for (int j=1;j<9;j++)
        {
            cin>>a[i][j];
        }
    }
    dfs(1);
    cout<<tmp;//tmp是全局变量
    return 0;
}