题意:八皇后问题,要求选取的总和最大
#include<stdio.h>
#include<iostream>
#include<sstream>
#include<queue>
#include<map>
#include<memory.h>
#include <math.h>
#include<time.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
const int N = 8;
int chess[N][N];
int final = -1;
int res[N];
void read()
{
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
cin >> chess[i][j];
}
void search(int cur, int sum)
{
if(cur == N)
{
if(sum > final)
final = sum;
return;
}
for(int i = 0; i < N; i++)
{
int ok = 1;
res[cur] = i;
for(int j = 0; j < cur; j++)
if(res[cur] == res[j] || cur - res[cur] == j - res[j]
|| cur + res[cur] == j + res[j])
{
ok = 0;
break;
}
if(ok)
{
search(cur + 1, sum + chess[cur][i]);
}
} }
int main()
{
freopen("d:\\1.txt", "r", stdin);
int k;
cin >> k;
while (k--)
{
read();
final = -1;
search(0,0);
printf("%5d\n",final);
}
return 0;
}