LeetCode 52 N-Queens II

    
        标签：
        
            LeetCode
        
            回溯法
        
    发布于：2020-06-07 16:41:35
    编辑于：2021-03-18 17:29:35
    浏览量：1314

分析

相比前一道题，这次我们只需求出数目即可。我们之前是使用一个完整的 board 直接保存棋子的位置来记录信息的，现在不使用 board，我们需要另一种节省空间的方法来保存必要信息来帮助我们判断某个位置是否可以落子。

我们需要的信息有：

某一列上已有棋子了吗？
正左上角已有棋子了吗？
正右上角已有棋子了吗？

对于第一点，显然一个长度为 n 的布尔数组足以解决问题。

对于第二点，斜线的表达式为 y=-x+b，即 b=x+y 是一个常量，我们可以使用该常量来唯一标记该向下的斜线，这意味着我们可以使用一个 2*n 的布尔数组来进行记录。

对于第三点，同第二点，不过 b=y-x。

代码

class Solution {
public:
    int count;
    int n;
    int totalNQueens(int n) {
        this->n = n;
        // true means occupied
        vector<bool> column(n, false);
        vector<bool> upperLeft(n, false);
        vector<bool> upperRight(n, false);
        backtrack(column, upperLeft, upperRight, 0);
        return count;
    }
private:
    void backtrack(vector<bool>& column, vector<bool>& upperLeft, vector<bool>& upperRight, int row) {
        if(row==n) {
            count++;
            return;
        }
        for(int col=0;col<n;++col){
            if(column[col]||upperLeft[row+col]||upperRight[n+row-col]) continue;
            column[col] = true;upperLeft[row+col] = true;upperRight[n+row-col]=true;
            backtrack(column, upperLeft, upperRight, row+1);
            column[col] = false;upperLeft[row+col] = false;upperRight[n+row-col]=false;
        }
    }
};

Links: LeetCode-52-N-Queens