努比亚和苏丹没有子女，所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明，所以他准备了一个西洋棋盘，上面的每个格子中均有一个 1−99 的数字。他又准备了 8 个皇后棋子。 皇后的规则就是不能有任何棋子同行或者同列或者同斜线，在满足这个规则的同时，王位继承者还需要让 8 个皇后所在的位置的数字的和是最大的。
输入格式 输入一个数字 k(k≤20)，代表棋盘的数量。接下来有 k 个棋盘，每个棋盘有 64 个数字，分成 8 行 8 列出入，具体可见样例，每一个数字均小于 100。
输出格式 每一个棋盘对应输出最大的数值， 一共输出 k 行。
样例输入 1 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
#include"iostream" #include"string.h" using namespace std; bool sign[8][8]; int ai[8][8]; //int num; int sum; int mmax; void dfs(int cur) { if(cur==8) { //num++; if(sum>mmax) mmax=sum; return ; } for(int i=0;i<8;i++) { sign[cur][i]=true; int j=0; for(;j<cur;j++) { if(sign[j][i]) { sign[cur][i]=false; break; } int hang=i-(cur-j); int hang1=i+(cur-j); if((sign[j][hang]&&hang>=0&&hang<8)||(sign[j][hang1]&&hang1>=0&&hang1<8)) { sign[cur][i]=false; break; } } if(j==cur) { sum+=ai[cur][i]; dfs(cur+1); sign[cur][i]=false; sum-=ai[cur][i]; } } } int main() { int n; cin>>n; while(n--) { //num=0; sum=0; mmax=-1e9; for(int i=0;i<8;i++) { for(int j=0;j<8;j++) { cin>>ai[i][j]; } } memset(sign,0,sizeof(sign)); dfs(0); //cout<<num<<endl; cout<<mmax<<endl; } return 0; }其实就是八皇后问题加了一个维护最大和的功能，几行代码而已
