大家好,又见面了,我是你们的朋友全栈君。
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;
}
程序运行结果:
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/187713.html原文链接:https://javaforall.cn