欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

领扣 52. N皇后 II

程序员文章站 2022-05-20 13:51:56
...

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给定一个整数 n,返回 n 皇后不同的解决方案的数量。

位运算解法 0ms (注:将设想的棋盘视为从右到左你,n-1,0)
原理可参考https://www.cnblogs.com/TenosDoIt/p/3801621.html

int limit,sum;
void dfs_bit(int lineb,int lb,int rb,int t,int n)
{
    if(t==n)
        sum++;
    else
    {
        int able_p=limit&(~(lineb|lb|rb));
        while(able_p!=0)
        {
            int p=able_p&(~able_p+1);
            able_p-=p;
            dfs_bit(lineb|p,(lb|p)<<1,(rb|p)>>1,t+1,n);
        }
    }
}
class Solution {
public:
    int totalNQueens(int n) {
        limit=(1<<n)-1;
        sum=0;
        dfs_bit(0,0,0,0,n);
        return sum;
    }
};
相关标签: 领扣