n皇后问题c语言代码_c语言序列求和输入两个正整数m和n

全栈程序员-站长 • 2022年9月29日下午8:16 • 未分类 • 阅读 3

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。(即任意两个皇后都不能处于同一行、同一列或同一斜线上).

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:输入: 4

输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

"解释: 4 皇后问题存在两个不同的解法。"

#include <iostream>
#include<vector>
#include<string>
using namespace std;
vector<vector<string> >res;
    void IsOk(int &row,int &col,int n,vector<vector<int> >&loca)
       //每加入一个Q则改变位置数组使得下次不可放置位置为1，以此作为判断
    {
        for(int i=0;i<n;++i){//加入位置同行同列
            if(!loca[row][i]) loca[row][i]=1;
            if(!loca[i][col]) loca[i][col]=1;
        }
        for(int i=0;i<n;++i)//同行位置左右对角线
            for(int j=0;j<n;++j)
                if(j==i-row+col||j==-i+row+col)
                    loca[i][j]=1;
    }
    void dfs(vector<string>ans,int depth,vector<vector<int> >flag)
    {
        if(depth==ans.size()) {
            res.push_back(ans);
            return ;
        }
        for(int i=0;i<ans.size();++i)
        {
            if(flag[depth][i]) continue;//如果此位置为1，则不可放置
            vector<vector<int> >temp=flag;
            ans[depth][i]='Q';
            IsOk(depth,i,ans.size(),flag);
            dfs(ans,depth+1,flag);//一行一行放置
            flag=temp; //返回上一层，所有改变数据还原
            ans[depth][i]='.';
        }
        return ;
    }
    void solveNQueens(int n) {
        if(n<=0) return ;
        vector<string>ans(n);
        vector<vector<int> >location(n,vector<int>(n));
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                ans[i]+='.';
                location[i][j]=0;
            }
        }
        dfs(ans,0,location);
        return ;
    }

int main()
{
    int n;
    cin>>n;
    solveNQueens(n);
    for(int i=0;i<res.size();++i){
            cout<<"第"<<i<<"种解法：\n";
        for(int j=0;j<res[i].size();++j)
        cout<<res[i][j]<<endl;
        cout<<endl;
    }
    return 0;
}

程序运行结果：

n皇后问题c语言代码_c语言序列求和输入两个正整数m和n