[数据结构与算法]LeetCode-51. N 皇后

一、题目

二、思路

1、皇后的限制：皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。（注意不只是相邻的两个，是整个矩阵的斜线）
2、采用回溯的方法，当当前条件满足时可以进行回溯
3、判断条件，注意是判断整个矩阵的一列、左上角的斜线、右上角的斜线，要用for循环，不能用if
4、当到达n层时，添加进去输出数组

三、代码

class Solution
{
public:
    vector<vector<string>> OutPut;
    vector<vector<string>> solveNQueens(int n)
    {
        vector<string> res;
        //把'.'重复n次
        string str = string(n, '.');
        for (int i = 0; i < n; ++i)
        {
            res.emplace_back(str);
        }
        backtrack(res, n, 0);
        return OutPut;
    }
    void backtrack(vector<string> &res, const int &n, int row)
    {
        if (row == n)
        {
            OutPut.emplace_back(res);
            return;
        }
        else if (row > n)
        {
            return;
        }
        for (int col = 0; col < n; ++col)
        {
            if (is_ok(res, row - 1, col, n))
            {
                res[row][col] = 'Q';
                backtrack(res, n, row + 1);
                res[row][col] = '.';
            }
        }
    }
    bool is_ok(vector<string> &res, int row, int col, int n)
    {
        //判断正上方一线
        for (int i = 0; i <= row; ++i)
        {
            if (res[i][col] == 'Q')
            {
                return false;
            }
        }
        //判断左上方斜线
        for (int i = row, j = col - 1; i >= 0 && j >= 0; --i, --j)
        {
            if (res[i][j] == 'Q')
            {
                return false;
            }
        }
        //判断在右上方
        for (int i = row, j = col + 1; i >= 0 && j < n; --i, ++j)
        {
            if (res[i][j] == 'Q')
            {
                return false;
            }
        }
        return true;
    }
};