LeetCode 52. N-Queens II – 柳婼の blog

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

分析：和LeetCode 51. N-Queens一样，只需改动几行代码即可~

class Solution {
    int cnt = 0;
public:
    int totalNQueens(int n) {
        vector<int> pos(n);
        dfs(pos, n, 0);
        return cnt;
    }
private:
    void dfs(vector<int> &pos, int n, int row) {
        if(row == n) {
            cnt++;
            return ;
        }
        for(pos[row] = 0; pos[row] < n; pos[row]++) {
            if(issafe(pos, n, row)) {
                dfs(pos, n, row + 1);
            }
        }
    }
    
    bool issafe(vector<int> &pos, int n, int row) {
        for(int i = 0; i < row; i++)
            if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))
                return false;
        return true;
    }
};

class Solution {

int cnt = 0;

public:

int totalNQueens(int n) {

vector<int> pos(n);

dfs(pos, n, 0);

return cnt;

}

private:

void dfs(vector<int> &pos, int n, int row) {

if(row == n) {

cnt++;

return ;

}

for(pos[row] = 0; pos[row] < n; pos[row]++) {

if(issafe(pos, n, row)) {

dfs(pos, n, row + 1);

}

bool issafe(vector<int> &pos, int n, int row) {

for(int i = 0; i < row; i++)

if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))

return false;

return true;

}

};

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版