N皇后-HDU2553

文章目录
  1. 1. N皇后问题
  2. 2. dfs常规解法代码
  3. 3. 重难点
  4. 4. 状态压缩+位运算解法
  5. 5. 参考

N皇后问题

在N*N的方格棋盘放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。
你的任务是,对于给定的N,求出有多少种合法的放置方法。

原题链接:N皇后

dfs常规解法代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

const int maxr = 11;
int n;
int queen[maxr];
int ans;

bool check(int r, int c)
{
    for (int i = 0; i < r; ++i)
        if (queen[i] == c || abs(queen[i] - c) == abs(i - r))
            return false;

    return true;
}

void dfs(int r)
{
    if (r == n)
    {
        ++ans;
        return;
    }

    for (int i = 0; i < n; ++i)
    {
        queen[r] = i;
        if (check(r, queen[r]))
            dfs(r + 1);
    }
}

int main()
{
    int answer[11] = {0};
    for (int i = 1; i <= 10; ++i)
    {
        memset(queen, 0, 11 * sizeof(int));
        n = i;
        ans = 0;
        dfs(0);
        answer[i] = ans;
    }

    while (scanf("%d", &n) != EOF)
    {
        if (n == 0)
            break;
        printf("%d\n", answer[n]);
    }

    return 0;
}

重难点

dfs函数:
参数r为当前搜索到的行数,当放置的皇后数量达到n个时ans+1。接着for一遍尝试当前行的0-n列是否可以放置皇后,使用check函数判断,若可以,则进入到下一行的dfs递归。

check函数:
参数r为当前要检查的皇后的行数,c同理为列数。接着for循环遍历已放置皇后是否与当前皇后冲突。
各变量含义:

         行      列
原皇后:  i  queen[i]
新皇后:  r     c

判断条件:

  1. 由于queen[i]代表第i行的皇后位置,故不会有冲突,无需判断。c == queen[i]判断是否同列
  2. abs(queen[i] - c) == abs(i - r)判断两个皇后的行之差列之差是否相等,相等则在同一对角线。

状态压缩+位运算解法

//to do..

参考

n皇后(回溯和剪枝)–HDU2553

分享到