非递归的八皇后C++
博客专区 > 侯禹 的博客 > 博客详情
非递归的八皇后C++
侯禹 发表于4年前
非递归的八皇后C++
  • 发表于 4年前
  • 阅读 101
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

其实就是利用了栈来实现DFS,用递归的方法虽然容易理解,但是容易有嵌套层数过多带来的问题,所以用栈更好一些

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
const int N = 8;
int x[N];
int num = 1;
void dayin()
{
    cout<<"num:"<<num++<<endl;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if(x[i]==j)cout<<"Q";
            else cout<<"#";
        }cout<<endl;
    }
}
bool isOk(int k)
{
    for(int i=1;i<k;i++)
    {
        if(x[i]==x[k]||fabs(i-k)==fabs(x[i]-x[k]))return false;
    }
    return true;
}
void DFS()
{
    int k=1;x[1]=0;
    while(k>0)
    {
        x[k]++;
        while(x[k]<=N&&!(isOk(k)))
        {
            x[k]++;
        }
        if(x[k]<=N)
        {
            if(k==N)dayin();
            else k++,x[k]=0;
        }
        else k--;
    }
}
int main(void)
{
    DFS();
    return 0;
}


  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 93
博文 49
码字总数 34362
×
侯禹
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: