HDUOJ 2553 N皇后问题 DFS深搜

这道题是典型的深搜类型的题。直接贴代码了。
但是有个需要注意的是，要先打表，不然会超时。

#include <iostream>
#include <memory.h>
using namespace std;
int flag[10][10];
int cnt, s;
void dfs(int depth);
void mark_for_unavailable(int, int);
void mark_for_available(int, int);
bool isAvailable(int, int);
int main()
{
    //因为N<=10, 所以这里先打表，之前没打表，数据量很大。超时了。
    int num[11];
    for(s = 1; s <= 10; ++s)
    {
        cnt = 0;
        memset(flag, -1, sizeof(flag));
        dfs(0);
        num[s] = cnt;
    }

    int n;
    while(cin >> n)
    {
        if(0 == n)
            break;
        cout << num[n] << endl;
    }
    return 0;
}

void dfs(int depth)  //深搜
{
    for(int i = 0; i < s; i++)
    {
        if(isAvailable(depth, i))
        {
            if(depth == s - 1) {cnt++; return;}
            mark_for_unavailable(depth, i);
            dfs(depth + 1);
            mark_for_available(depth, i);
        }
    }
}

void mark_for_unavailable(int i, int j) //标记行列，对角线为不可放皇后
{
    for(int k = i; k < s; ++k) if(-1 == flag[k][j]) flag[k][j] = i;
    for(int k = 0; k < s; ++k) if(-1 == flag[i][k]) flag[i][k] = i;
    for(int k = i, p = j; k < s && p >= 0; ++k, --p) if(-1 == flag[k][p]) flag[k][p] = i;
    for(int k = i, p = j; k < s && p < s; ++k, ++p) if(-1 == flag[k][p]) flag[k][p] = i;
}
void mark_for_available(int i, int j)  //取消标记
{
    for(int k = i; k < s; ++k) if(i == flag[k][j]) flag[k][j] = -1;
    for(int k = 0; k < s; ++k) if(i == flag[i][k]) flag[i][k] = -1;
    for(int k = i, p = j; k < s && p >= 0; ++k, --p) if(i == flag[k][p]) flag[k][p] = -1;
    for(int k = i, p = j; k < s && p < s; ++k, ++p) if(i == flag[k][p]) flag[k][p] = -1;
}
bool isAvailable(int i, int j) //判断是否可以放皇后
{
    if(-1 == flag[i][j])
        return true;
    return false;
}

另外在该题的Discuss里面看到一份很牛的代码，我没怎么看懂。
使用的是位运算。

#include <iostream>
#include <cstdio>
using namespace std;
int sum,upperlim,n;
int ans[15];
void queen(int row, int ld, int rd)
{
    int pos,p;
    if(row != upperlim)
    {
        pos = upperlim & (~(row | ld | rd));
        while(pos != 0)
        {
            p = pos & (-pos);
            pos = pos - p;
            queen(row+p, (ld+p)<<1, (rd+p)>>1);
        }
    }
    else
        sum++;
}
int main()
{
    for(int i=1; i<=10; i++)
    {
        upperlim = (1 << i) - 1;
        sum = 0;
        queen(0,0,0);
        ans[i] = sum;
    }
    while(scanf("%d",&n),n)
    {
        cout<<ans[n]<<endl;
    }
    return 0;
}