[HDU 2553] N皇后问题

佚名 6年前 (2019-05-06) 随笔 1549人围观抢沙发百度已收录

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2553

关于八皇后问题的参考链接：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

AC代码：

#include <cstdio>

using namespace std;

const int maxn = 110;

int vis[3][maxn];
int sum;
int dp[11];

void DFS(int row, int n) {
    if (row == n + 1)
        sum++;
    else {
        for (int i = 1; i <= n; i++) {
            if (!vis[0][i] && !vis[1][row + i] && !vis[2][row - i + n]) {
                vis[0][i] = vis[1][row + i] = vis[2][row - i + n] = true;
                DFS(row + 1, n);
                vis[0][i] = vis[1][row + i] = vis[2][row - i + n] = false;
            }
        }
    }
}

int main() {
    for (int i = 1; i <= 10; i++) {
        sum = 0;
        DFS(1, i);
        dp[i] = sum;
    }
    int n;
    while (scanf("%d", &n) != EOF && n != 0) {
        printf("%d\n", dp[n]);
    }
    return 0;
}