解题思路

dfs回溯+vector<string>数组初始化

棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度

• 如何模拟皇后之间是否会攻击的限制条件

代码

class Solution {
public:
    vector<vector<string>> res;

    bool check(int r, int c, vector<string>& g, int n)
    {
        // 不能同行
        // 不能同列
        // 不能同斜线

        // 因为每次递归只能选择一行中的一个位置，所以不用判断是否同行
        for (int i = 0; i < c; i++)
            if (g[r][i] == 'Q') return false;

        for (int i = 0; i < r; i++) // 剪枝: n-->r
            if (g[i][c] == 'Q') return false;

        // 不能同斜线，两个斜线，右下到左上
        for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--,j--)
            if (g[i][j] == 'Q') return false;
        // 左下到右上
        for (int i = r - 1, j = c + 1; i >= 0 && j < n; i--,j++)
            if (g[i][j] == 'Q') return false;

        return true;
    }

    void dfs(int n, int k, vector<string>& g) // n行n列，当前枚举第k行
    {
        if (k == n)// k 枚举[0, n-1]行，当k=n时，直接返回。棋盘的高度，递归的深度
        {
            res.push_back(g);
            return;
        }

        for (int i = 0; i < n; i++) // 棋盘的宽度，for循环的宽度
        {
            if (check(k, i, g, n)) // 判断g[k][i]位置放皇后是否合法
            {
                g[k][i] = 'Q';
                dfs(n, k + 1, g);
                g[k][i] = '.';
            }
        }

    }
    vector<vector<string>> solveNQueens(int n) {

        // 数组初始化
        vector<string> g(n, string(n, '.')); // g 是n*n的矩阵
        dfs(n, 0, g); // 共n行，从第0行开始遍历
        return res;
    }
};