N皇后问题

[编程题]N皇后问题

热度指数：2297 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行，不同列也不再同一条斜线上，求给一个整数n，返回n皇后的摆法。

输入描述:

输出一个整数，代表n。

输出描述:

输出一个整数，代表n皇后的种数。

示例1

输入

输出

示例2

输入

输出

备注:

时间复杂度，空间复杂度

算法知识视频讲解

helloxuanbao

#include <stdio.h>

typedef unsigned int uint;

uint proc(uint mask, uint colPut, uint leftLim, uint rightLim) {
    if (mask == colPut) {
        return 1;
    }
    uint ans = 0, pos, mostRight;
    pos = mask & (~(colPut | leftLim | rightLim));
    while (pos != 0) {
        mostRight = pos & (~pos + 1);
        pos -= mostRight;
        ans += proc(mask, colPut | mostRight,
                    (leftLim | mostRight) << 1,
                    (rightLim | mostRight) >> 1);
    }
    return ans;
}

int main(void) {
    int n;
    scanf("%d", &n);
    uint mask = (1 << n) - 1;
    printf("%u\n", proc(mask, 0, 0, 0));
    return 0;
}

发表于 2022-01-29 20:12:23 回复(0)