首页 > 其他 > 详细

【HDU2553】n皇后

时间:2020-06-30 22:35:00      阅读:13      评论:0      收藏:0      [点我收藏+]

标签:情况   减少   lap   art   ble   while   

题链

tips:

  1.n皇后其实是用递归遍历所有可能的情况,通过位置的限制来减小解空间的大小,减少枚举的数目。属于递归以枚举。

  2.是递归完成全排列的基础上改的。

  3.有一维和剪枝的写法(待补)

  4.假设到一般情况,写流程(函数)。如本题:假设当前枚举到第index行。

技术分享图片
#include<cstdio>
#include<cmath>
#include<algorithm>

const int maxn=11;
int n,P[maxn],hashTable[maxn]={false};
int cnt=0;
int ans[maxn];

//好多分析时都是假设到n,即中间某一一般化的状态
//假设当前要确定第index行的放置位置
void generateP(int index){
    if(index == n+1){
       bool flag=true;
       //检验i行的列和j行的列放置是否矛盾
       //已经排除了同行同列的情形,只需检验对角线即可
       for(int i=1;i<=n; i++){
        for(int j=i+1;j<=n;j++){
            if(abs(i-j)==abs(P[i]-P[j])) flag=false;//几何关系转换成下标关系
        }
       }
       if(flag) cnt++;
       return;
    }
    //每一层都是从1开始枚举的,上下层并不矛盾
    for(int x=1;x<=n;x++){
        if(hashTable[x]==false ){
            P[index]=x;//index行的皇后放在x列
            hashTable[x]=true;
            generateP(index+1);
            hashTable[x]=false;
        }
    }
}

int main(){
    //先预处理,打出表来
    for(int i=1;i<=10;i++){
        n=i;
        generateP(1);
        ans[i]=cnt;
        cnt=0;
    }

    //输入
    while(scanf("%d",&n)!=EOF && n){
        printf("%d\n",ans[n]);
    }

    return 0;
}
View Code

ref:

  1.胡凡的算法笔记

  2.博客

https://blog.csdn.net/Hackbuteer1/article/details/6657109

 

【HDU2553】n皇后

标签:情况   减少   lap   art   ble   while   

原文:https://www.cnblogs.com/SUMaywlx/p/13216236.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号