LeetCode-51-N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

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

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

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

示例:

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

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

Code

//时间复杂度O(!n)
//空间复杂度O(n)用于申请的记录每行选取位置的数组nums
class Solution {
private:
    vector<vector<string>> res;
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> temp;
        //开辟n大小的数组，初始化为-1
        //用于申请的记录每行选取位置的数组nums
        vector<int> nums(n, -1);
        DFS(0, n, temp, nums);
        return res;
    }

    void DFS(int deepth,int n,vector<string>& temp,vector<int>& nums){
    	//递归终止条件
        if(deepth==n){
            res.push_back(temp);
            return;
        }
        //初始化长度为n的.字符串
        string s(n,'.');
        for(int i=0;i<n;i++){
            s[i]='Q';
            temp.push_back(s);
            //判断是否可以放置皇后
            if(isValid(deepth,i,nums)){
                nums[deepth] = i;
                //带着当前的结果去下一层找
                DFS(deepth+1,n,temp,nums);
            }
            if (nums[deepth] != -1)
                nums[deepth] = -1;
            s[i]='.';
            temp.pop_back();
        }       
    }

	//判断位置是否可用
    bool isValid(int row, int col, vector<int>& nums) {
        //检测当前列是否用过
        for (int i = 0;i < nums.size();i++) {
            //第i行已经用过col列或row,col处于i行皇后的对角线位置
            if (nums[i] == col || (nums[i] != -1&&abs(row - i) == abs(col - nums[i])))
                return false;
        }
        return true;
    }
};