N皇后

N皇后问题

http://www.nowcoder.com/questionTerminal/c76408782512486d91eea181107293b6

思路

  1. 列,对角线,斜对角线是否可放棋子分别用二进制数表示
  2. 每次枚举可放棋子的列,使用lowbit运算

参考链接

https://zhuanlan.zhihu.com/p/22846106

class Solution {
private:
    int cnt = 0;
    int col;
    int dg;
    int udg;
    map<int, int> mp;
public:
    /**
     *
     * @param n int整型 the n
     * @return int整型
     */
    int lowbit(int x){
        return x & -x;
    }

    void dfs(int x, int &n){
        int avail = col & (dg >> x) & (udg >> (n-x));
        for(int y=avail;y;y -= lowbit(y)){
            if(x == n-1) cnt++;
            else{
                int t = mp[lowbit(y)];
                col -= 1 << t;
                dg -= 1 << (x + t);
                udg -= 1 << (t - x + n);
                dfs(x+1, n);
                col += 1 << t;
                dg += 1 << (x + t);
                udg += 1 << (t - x + n);
            }
        }
    }

    int Nqueen(int n) {
        for(int i=0;i<n;i++) mp[1 << i] = i;
        col = (1 << n) - 1;
        dg = udg = (1 << (2*n)) - 1;
        dfs(0, n);
        return cnt;
    }
};
全部评论

相关推荐

小火柴燃烧吧:接啊,接了之后反手在咸鱼找个大学生搞一下,量大从优
点赞 评论 收藏
分享
10-07 23:57
已编辑
电子科技大学 Java
八街九陌:博士?客户端?开发?啊?
点赞 评论 收藏
分享
6 收藏 评论
分享
牛客网
牛客企业服务