solution.md

# N皇后 II
<div class="notranslate">
    <p><strong>n&nbsp;皇后问题</strong> 研究的是如何将 <code>n</code>&nbsp;个皇后放置在 <code>n×n</code> 的棋盘上，并且使皇后彼此之间不能相互攻击。</p>

    <p>给你一个整数 <code>n</code> ，返回 <strong>n 皇后问题</strong> 不同的解决方案的数量。</p>

    <p>&nbsp;</p>

    <div class="original__bRMd">
        <div>
            <p><strong>示例 1：</strong></p>
            <img style="width: 600px; height: 268px;" src="https://assets.leetcode.com/uploads/2020/11/13/queens.jpg"
                alt="">
            <pre><strong>输入：</strong>n = 4
<strong><br />输出：</strong>2
<strong><br />解释：</strong>如上图所示，4 皇后问题存在两个不同的解法。
    </pre>

            <p><strong>示例 2：</strong></p>

            <pre><strong>输入：</strong>n = 1
<strong><br />输出：</strong>1
    </pre>

            <p>&nbsp;</p>

            <p><strong>提示：</strong></p>

            <ul>
                <li><code>1 &lt;= n &lt;= 9</code></li>
                <li>皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。</li>
            </ul>
        </div>
    </div>
</div>
<p>以下错误的选项是？</p>
## aop
### before
```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after
```cpp
int main()
{
    Solution sol;
    int n = 4;
    int res;

    res = sol.totalNQueens(n);
    cout << res;
    return 0;
}
```

## 答案
```cpp
class Solution
{
public:
    int totalNQueens(int n)
    {
        int res = 0;
        int queenPos[100];
        NQueen(res, n, 0, queenPos);
        return res;
    }
    void NQueen(int &res, int N, int k, int queenPos[])
    {
        int i;
        if (k == N)
        {
            res++;
            return;
        }
        for (i = 0; i < N; i++)
        {
            int j;
            for (j = 0; j < k; j++)
            {
                if (queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j))
                {
                    break;
                }
            }
            if (j == k)
            {
                queenPos[k] = i;
                NQueen(res, N, k, queenPos);
            }
        }
    }
};

```
## 选项

### A
```cpp
class Solution
{
public:
    int totalNQueens(int n)
    {
        vector<int> stack(n);
        return dfs(n, 0, stack);
    }

private:
    int dfs(int n, int row, vector<int> &stack)
    {
        int count = 0;
        if (row == n)
        {
            return count + 1;
        }
        else
        {
            for (int i = 0; i < n; i++)
            {
                if (row == 0 || !conflict(stack, row, i))
                {
                    stack[row] = i;
                    count += dfs(n, row + 1, stack);
                }
            }
            return count;
        }
    }
    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:
    void recurse(vector<string> solution, int pos, vector<vector<bool>> validPos, int &result)
    {
        int n = solution[0].size();
        if (pos == n)
        {
            result++;
            return;
        }

        for (int i = 0; i < n; i++)
        {
            if (!validPos[pos][i])
                continue;

            vector<vector<bool>> newPos = validPos;
            for (int j = pos; j < n; j++)
            {
                newPos[j][i] = false;
                if (i - j + pos >= 0)
                    newPos[j][i - j + pos] = false;
                if (i + j - pos < n)
                    newPos[j][i + j - pos] = false;
            }
            solution[pos][i] = 'Q';

            recurse(solution, pos + 1, newPos, result);
            solution[pos][i] = '.';
        }

        return;
    }

    int totalNQueens(int n)
    {
        int result = 0;
        vector<string> solution(n, string(n, '.'));
        vector<vector<bool>> validPos = vector<vector<bool>>(n, vector<bool>(n, true));

        recurse(solution, 0, validPos, result);

        return result;
    }
};
```

### C
```cpp
class Solution
{
public:
    bool isvalid(vector<string> &temp, int i, int j)
    { //判断棋盘是否有效
        //for (int k = 0; k<temp[i].size(); ++k){//判断行。不用判断行了，每行放一个之后就会递归到下一行了
        //	if (temp[i][k] == 'Q') return false;
        //}
        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;
    }

    int dfs(int &count, vector<string> &temp, int i, int n)
    {
        if (i == n)
            return ++count;

        for (int j = 0; j < n; ++j)
        {
            if (isvalid(temp, i, j))
            {
                temp[i][j] = 'Q'; //递归前修改
                dfs(count, temp, i + 1, n);
            }
            temp[i][j] = '.'; //递归后恢复
        }
        return count;
    }

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