[LeetCode 52] N-Queens II

这一题就是上一题的简化版了，我们只针对上面的算法2来求解这一题 class Solution { public: int totalNQueens(int n) { vector state(n, -1); res = 0; solver(state, 0); return res; } void solver(vector &state, int row){ //放置第row行的皇后 int n = state.size(); if(row == n){ res++; return; } for(int col = 0; col < n; col++) if(isValid(state, row, col)){ state[row] = col; solver(state, row + 1); state[row] = -1;; } }

//判断在row行col列位置放一个皇后，是否是合法的状态
//已经保证了每行一个皇后，只需要判断列是否合法以及对角线是否合法。
bool isValid(vector<int> &state, int row, int col){
    for(int i = 0; i < row; i++)//只需要判断row前面的行，因为后面的行还没有放置
        if(state[i] == col || abs(row - i) == abs(col - state[i]))
            return false;
    return true;
}

private: int res; };

class Solution { public: int totalNQueens(int n) { vector col; int totSol = 0; solveNQ(n, 0, col, totSol); return totSol; }

void solveNQ(int n, int irow, vector<int> &col, int &totSol) {
    if(irow == n) {
        totSol++;
        return;
    }

    for(int icol = 0; icol < n; ++icol) {
        if(validPos(col, irow, icol)) {
            col.push_back(icol);
            solveNQ(n, irow + 1, col, totSol);
            col.pop_back();
        }
    }
}

bool validPos(vector<int> &col, int irow, int icol) {
    if(irow < col.size()) return false;
    for(int i = 0; i < col.size(); i++) {
        if(icol == col[i] || abs(irow - i) == abs(icol - col[i]))
            return false;
    }
    return true;
}    

};