uva-167 - The Sultan's Successors-八皇后-回溯

本文主要是介绍uva-167 - The Sultan's Successors-八皇后-回溯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一道变异的八皇后问题，八皇后问题是很经典的回溯题目；

利用L，R，LL，RR数组标记点的横排，竖排，左斜，右斜有没有皇后。

从i=1，开始找，如果找到i=8以后，看一下统计的和，取其中的最大值。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
using namespace std;
int map[10][10];
int l[8];
int r[8];
int ll[20];
int rr[20];
int sum=0;
int sum_max;
void get(int i)
{int j;if(i>8){if(sum>sum_max)sum_max=sum;return ;}for(j=1;j<=8;j++){if(l[i]&&r[j]&&ll[i-j+8]&&rr[i+j]){l[i]=0;r[j]=0;ll[i-j+8]=0;rr[i+j]=0;sum+=map[i][j];get(i+1);l[i]=1;r[j]=1;ll[i-j+8]=1;rr[i+j]=1;sum-=map[i][j];}}
}
int main()
{int T,i,j;scanf("%d",&T);while(T--){for(i=1;i<=8;i++){for(j=1;j<=8;j++){scanf("%d",&map[i][j]);}}memset(l,1,sizeof(l));memset(r,1,sizeof(r));memset(ll,1,sizeof(ll));memset(rr,1,sizeof(rr));sum=0;sum_max=0;get(1);printf("%5d\n",sum_max);}return 0;
}

这篇关于uva-167 - The Sultan's Successors-八皇后-回溯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---