题目 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例：
输入： 4
输出：
[[".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."]]解释: 4 皇后问题存在两个不同的解法。
提示： 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
代码：
#include <stdio.h> #include <iostream> #include <vector> #include <cstring> using namespace std; class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<vector<string>> ans; vector<string> oneans(n,string(n,'.'));//创建一个解 dfs(0,n,oneans,ans); return ans; } void dfs(int row,int n,vector<string>& oneans,vector<vector<string>> &ans){ if(row == n){ //所有行都放了皇后 ans.push_back(oneans);//把解放入最后解中 return ; } for(int col=0;col<n;col++){ if(isValid(row,col,oneans,n)){ oneans[row][col] = 'Q'; //放入 dfs(row+1,n,oneans,ans);//每一次在行=row的数组中放皇后，进入下一行 oneans[row][col] = '.'; //回溯 不放 } } } bool isValid(int row,int col,vector<string>& oneans,int n){ //同一行无需检测 每一次在行=row的数组中放皇后，进入下一行 // for(int i=0;i<n;i++) // if(oneans[row][i]=='Q'&&i!=col) // return false; //同一列 for(int i=0;i<n;i++) if(oneans[i][col]=='Q') return false; //主对角线 for(int x = row-1,y = col-1;x>=0&&y>=0;x--,y--) if(oneans[x][y]=='Q') return false; //副对角线 for(int x = row-1,y = col+1;x>=0&&y<n;x--,y++) if(oneans[x][y]=='Q') return false; return true; } }; int main() { int n=6; Solution s; vector<vector<string>> ans = s.solveNQueens(n); for(int i=0;i<ans.size();i++){ for(int j =0;j<ans[i].size();j++) cout<<ans[i][j]<<endl; } return 0; }今天也是爱zz的一天哦！
