算法设计与分析（三）回溯法---八皇后问题（包含全排列）

2021-02-16 06:18

阅读：613

标签：clu ref 排列组合 ring 实现 ext segment cpp 回溯

全排序问题：输入一个按字符序升序的无重复字母字符串，输出所有按字典升序的排列组合

#include
#include
#include
#include
using namespace std;
string s;
map mp;
void swap(char &x,char &y){
    char temp=x;
    x=y;
    y=temp;
}
void dfs(int now){
    if(now==s.size()){
        mp[s]=1;
        return ;
    }
    for(int i=now;i>s;
    dfs(0);
    for(auto i=mp.begin();i!=mp.end();i++){
        coutfirst

C++STL中的全排列函数为两个：next_permutation和prev_permutation
其中：next_permutation实现升序，而prev_permutation实现降序

https://blog.csdn.net/boliu147258/article/details/89376953

而八皇后问题由于可以简化为一个八位的排列问题，故可以用全排列构建解空间（实际上全排列也是DFS）

https://blog.csdn.net/schuffel/article/details/88951440

附上用普通方法

https://segmentfault.com/a/1190000003733325

#include

int count = 0;
int isCorrect(int i, int j, int (*Q)[4])
{
    int s, t;
    for(s=i,t=0; t=0&&t>=0; s--,t--)
        if(Q[s][t]==1)
            return 0;//判断左上方
    for(s=i+1,t=j+1; s=0&&t=0; s++,t--)
        if(Q[s][t]==1)
            return 0;//判断左下方

    return 1;//否则返回
}

void Queue(int j, int (*Q)[4])
{
    int i,k;
    if(j==4){//递归结束条件
        for(i=0; i

算法设计与分析（三）回溯法---八皇后问题（包含全排列）

标签：clu ref 排列组合 ring 实现 ext segment cpp 回溯

原文地址：https://www.cnblogs.com/yasheng/p/12709705.html

上一篇：Go语言中 Print，Println 和 Printf 的区别

下一篇：Java 实例级别的锁和类级别的锁

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：算法设计与分析（三）回溯法---八皇后问题（包含全排列）
文章链接：http://soscw.com/index.php/essay/55964.html

亲，登录后才可以留言！

算法设计与分析（三）回溯法---八皇后问题（包含全排列）

评论

热门文章

推荐文章

最新文章

置顶文章