LeetCode/N-Queens II.cpp at master · fuwutu/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution
{
public:
    int totalNQueens(int n)
    {
        vector<int> rowpos(n);
        int count = 0;
        dps(rowpos, 0, count);
        return count;
    }

    void dps(vector<int>& rowpos, int row, int& count)
    {
        int n = rowpos.size();
        for (int p = 0; p < n; ++p)
        {
            int i = 0;
            for (; i < row; ++i)
            {
                if (rowpos[i] == p || rowpos[i] + i == p + row || rowpos[i] - i == p - row)
                {
                    break;
                }
            }
            if (i == row)
            {
                rowpos[row] = p;
                if (row < n - 1)
                {
                    dps(rowpos, row + 1, count);
                }
                else
                {
                    count += 1;
                }
            }
        }
    }
};