现在的位置: 首页 > 综合 > 正文

N皇后

2013年12月12日 ⁄ 综合 ⁄ 共 499字 ⁄ 字号 评论关闭

第一次写。。以前刚学搜索都没写过, 这次刷USACO直接位运算, 没想到代码可以这么短。。。算6到13还是没问题的

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

using namespace std;

int n;
int ans;
int a[100];
void dfs(int row, int ld, int rd, int hd)
{
    if(row==n)
    {
        if(ans<3)
            for (int i=0; i<n; ++i)
                printf("%d%c", a[i], i==n-1?'\n':' ');
        ans++;
        return ;
    }
    for (int i=0, c=1; i<n; ++i, c<<=1)
    {
        int now=ld|rd|hd;
        if((~now)&c)
        {
            a[row]=i+1;
            dfs(row+1, (ld|c)<<1, (rd|c)>>1, hd|c);
        }
    }
}

int main ()
{
    scanf("%d", &n);
    ans=0;
    dfs(0, 0, 0, 0);
    printf("%d\n", ans);
    return 0;
}

抱歉!评论已关闭.