N皇后

问题描述： n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 上图为 8 皇后问题的一种解法。

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

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

示例： 输入：4 输出：[ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”],

["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ] 解释: 4 皇后问题存在两个不同的解法。

提示： 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-queens

class Solution { public: vector<vector<string>> res; void dfs(int n,int row,vector<int> &pos,vector<string> &tmp){ if(row==n){//如果当前行数等于n 说明已经遍历到最后一行了 此时已经是一个正确结果 res.push_back(tmp); return ; } for(int i=0;i<n;i++){ //查找对应的每一列 int j; for(j=0;j<row;j++){ //查找之前遍历过的行 //i代表列 j代表行 pos[]的值代表列 下标代表行 //判断是否同列或者同对角线 if(pos[j]==i||abs(row-j)==abs(i-pos[j])){ break; } } if(j==row){ pos[row]=i; tmp[row][i]='Q'; dfs(n,row+1,pos,tmp); tmp[row][i]='.'; } } } vector<vector<string>> solveNQueens(int n) { vector<int> pos(n,0); vector<string> tmp(n,string(n,'.')); dfs(n,0,pos,tmp); return res; } };