LeetCode 52. N-Queens II题目解析-wowAC

Description

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

题目复述

同样是n皇后问题,给定n,返回n皇后问题的方案数。

题目解析

在做这题的时候发现LeetCode 51.N-Queens的代码可以完美Accepted,然而还是想一下比较快速简洁的方法比较好。我们仍然按照行进行深度优先遍历,考虑使用比特位来表示当前已经占用的列col,对角线zhu以及副对角线fu,如下图

image.png

其中1表示已经被占,0表示空着,col为1的表示因为列的影响当前行不能放置的位置,zhu和fu表示因为主对角线和副对角线的影响导致当前行不能放置的位置,can表示当前行可以放置的位置,显然can = ~(col | zhu | fu)&mask,对于can中每一个1的位置lowbit,对于下一行的col,zhu,fu分别为col|lowbit,(zhu|lowbit)>>1以及((fu|lowbit)<<1)&mask。

    /*
    *参数:
    *row:当前要放置皇后的行
    *n:棋盘大小
    *col:行的放置情况
    *zhu:主对角线放置情况
    *fu:副对角线的放置情况
    */
    int dfs(int row, int n, int col, int zhu, int fu) {
        if(row == n) {
            return 1;
        }
        int mask = (1<<n)-1; //mask为全1,屏蔽高于n的1
        int can = (~(col | zhu | fu))&mask;
        int res = 0;   //方案数
        while(can) {
            int lowbit = can&(-can); //获取can的最低位1
            res += dfs(row+1, n, col|lowbit, (zhu|lowbit)>>1, ((fu|lowbit)<<1)&mask);
            can = can&(can-1);   //去除can的最低位1
        }
        return res;
    }
    
    int totalNQueens(int n) {
        
        return dfs(0, n, 0, 0, 0);
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注