solution.md

# N 皇后

<p><strong>n 皇后问题</strong> 研究的是如何将 <code>n</code> 个皇后放置在 <code>n×n</code> 的棋盘上，并且使皇后彼此之间不能相互攻击。</p><p>给你一个整数 <code>n</code> ，返回所有不同的 <strong>n<em> </em>皇后问题</strong> 的解决方案。</p><div class="original__bRMd"><div><p>每一种解法包含一个不同的 <strong>n 皇后问题</strong> 的棋子放置方案，该方案中 <code>'Q'</code> 和 <code>'.'</code> 分别代表了皇后和空位。</p><p> </p><p><strong>示例 1：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0051.N-Queens/images/queens.jpg" style="width: 600px; height: 268px;" /><pre><strong>输入：</strong>n = 4<strong><br />输出：</strong>[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]<strong><br />解释：</strong>如上图所示，4 皇后问题存在两个不同的解法。</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>n = 1<strong><br />输出：</strong>[["Q"]]</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>1 <= n <= 9</code></li>	<li>皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。</li></ul></div></div>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```

### after

```cpp
int main()
{
    Solution sol;
    int n = 4;
    vector<vector<string>> res;

    res = sol.solveNQueens(n);
    for (auto i : res)
    {
        for (auto j : i)
            cout << j << " ";
        cout << endl;
    }
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    bool isvalid(vector<string> &temp, int i, int j)
    {

        for (int k = 0; k < i; ++k)
        {
            if (temp[k][j] == 'Q')
                return false;
        }
        for (int p = i - 1, q = j - 1; p >= 0 && q >= 0; --p, --q)
        {
            if (temp[p][q] == 'Q')
                return false;
        }
        for (int p = i - 1, q = j + 1; p >= 0 && q < temp.size(); --p, ++q)
        {
            if (temp[p][q] == 'Q')
                return false;
        }
        return true;
    }

    void dfs(vector<vector<string>> &re, vector<string> &temp, int i, int n)
    {
        if (i == n)
        {
            re.push_back(temp);
            return;
        }
        for (int j = 0; j < n; ++j)
        {
            if (isvalid(temp, i, j))
            {
                temp[i][j] = 'Q';
                dfs(re, temp, i, n);
            }
            temp[i][j] = '.';
        }
        return;
    }

    vector<vector<string>> solveNQueens(int n)
    {
        vector<vector<string>> re;
        string aa;
        for (int i = 0; i < n; ++i)
            aa += '.';
        vector<string> temp(n, aa);
        dfs(re, temp, 0, n);
        return re;
    }
};

```
## 选项


### A

```cpp
class Solution
{
public:
    vector<vector<string>> solveNQueens(int n)
    {
        vector<vector<string>> res;
        vector<int> stack(n);
        vector<string> solution(n, string(n, '.'));
        dfs(n, 0, stack, solution, res);
        return res;
    }

private:
    void dfs(int n, int row, vector<int> &stack, vector<string> &solution, vector<vector<string>> &res)
    {
        if (row == n)
        {
            res.push_back(solution);
        }
        else
        {
            for (int i = 0; i < n; i++)
            {
                if (row == 0 || !conflict(stack, row, i))
                {
                    solution[row][i] = 'Q';
                    stack[row] = i;
                    dfs(n, row + 1, stack, solution, res);
                    solution[row][i] = '.';
                }
            }
        }
    }
    bool conflict(vector<int> &stack, int row, int col)
    {
        for (int i = 0; i < row; i++)
        {
            if (col == stack[i] || abs(row - i) == abs(col - stack[i]))
            {
                return true;
            }
        }
        return false;
    }
};
```

### B

```cpp
class Solution
{
public:
    vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n)
    {
        vector<string> board(n, string(n, '.'));
        backtrack(board, 0);
        return res;
    }

    void backtrack(vector<string> &board, int row)
    {
        if (row == board.size())
        {
            res.push_back(board);
            return;
        }
        int n = board[row].size();
        for (int col = 0; col < n; col++)
        {
            if (!isValid(board, row, col))
            {
                continue;
            }
            board[row][col] = 'Q';
            backtrack(board, row + 1);
            board[row][col] = '.';
        }
    }

    bool isValid(vector<string> &board, int row, int col)
    {
        int n = board.size();
        for (int i = 0; i < row; i++)
        {
            if (board[i][col] == 'Q')
            {
                return false;
            }
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
        {
            if (board[i][j] == 'Q')
            {
                return false;
            }
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        {
            if (board[i][j] == 'Q')
            {
                return false;
            }
        }
        return true;
    }
};
```

### C

```cpp
class Solution
{
public:
    bool isValue(vector<int> &pos, int row, int col)
    {
        for (int i = 0; i < row; ++i)
        {
            if (col == pos[i] || abs(row - i) == abs(col - pos[i]))
                return false;
        }
        return true;
    }
    void solveNQueensDFS(vector<int> &pos, int row, vector<vector<string>> &ans)
    {
        int n = pos.size();
        if (row == n)
        {
            vector<string> tmp(n, string(n, '.'));
            for (int i = 0; i < n; ++i)
                tmp[i][pos[i]] = 'Q';
            ans.push_back(tmp);
        }
        else
        {
            for (int col = 0; col < n; ++col)
            {
                if (isValue(pos, row, col))
                {
                    pos[row] = col;
                    solveNQueensDFS(pos, row + 1, ans);
                    pos[row] = -1;
                }
            }
        }
    }
    vector<vector<string>> solveNQueens(int n)
    {
        vector<int> pos(n, -1);
        vector<vector<string>> ans;
        solveNQueensDFS(pos, 0, ans);
        return ans;
    }
};
```