52. N 皇后 II#

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

3
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
4

5
示例 1：
6

7
输入：n = 4
8
输出：2
9
解释：如上图所示，4 皇后问题存在两个不同的解法。
10

11
示例 2：
12

13
输入：n = 1
14
输出：1
15

16

17
提示：
18

19
1 <= n <= 9
20
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

1
class Solution {
2
private:
3
    vector<int> res;
4
    int ans = 0;
5
public:
6
    void dfs(vector<int>& res, int col, int row)
7
    {
8
        if(col == row) ans++;
9
        for(int i = 0; i < row; i++)
10
        {
11
            if (judge(res, i))
12
            {
13
                res.push_back(i);
14
                dfs(res, col + 1, row);
15
                res.pop_back();
16
            }
17
        }
18
    }
19

20
    bool judge(vector<int> res, int n)
21
    {
22
        for(int i = 0; i < res.size(); i++)
23
        {
24
            if ((abs(res[i] - n) == res.size() - i) || n == res[i]) return false;
25
        }
26
        return true;
27
    }
28

29
    int totalNQueens(int n) {
30
        /* vector<int> res = {1, 0, 0 ,2, 10, 4, 40, 92, 352};
31
        return res[n - 1]; */
32
        dfs(res, 0, n);
33
        return ans;
34
    }
35
};