首页 > 代码库 > careercup-递归和动态规划 9.9
careercup-递归和动态规划 9.9
9.9 设计一种算法，打印八皇后在8*8棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
类似leetcode：N-Queens
回溯法的实现代码：
#include<vector>#include<iostream>#include<string>using namespace std;bool isValid(vector<string> &path,int row,int col){ int i,j; for(j=0;j<row;j++) if(path[j][col]==‘Q‘) return false; //由于不一定是主对角线和副对角线上的点，所以i和j的初值不能从0或者最后一个点赋值 for(i=row-1,j=col-1;i>=0&&j>=0;i--,j--) if(path[i][j]==‘Q‘) return false; for(i=row-1,j=col+1;i>=0&&j<(int)path.size();i--,j++) if(path[i][j]==‘Q‘) return false; return true;}void helper(int n,int start,vector<vector<string> > &res,vector<string> &path){ if(start==n) { res.push_back(path); return; } int j; for(j=0;j<n;j++) { if(isValid(path,start,j)) { path[start][j]=‘Q‘; helper(n,start+1,res,path); path[start][j]=‘.‘; } }}vector<vector<string> > NQueue(int n){ vector<vector<string> > res; vector<string> str(n,string(n,‘.‘)); helper(n,0,res,str); return res;}int main(){ vector<vector<string> > result=NQueue(4); for(auto a:result) { for(auto t:a) cout<<t<<endl; cout<<endl; }}
careercup-递归和动态规划 9.9
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。