HDU 2553 N皇后问题

都说不做8皇后,人生不完整.

作为回溯,递归的入门题,倒是看过很多类似的题解.

今天自己写一遍,用到了以前看某Blog上的一维数组表示棋盘.代码写得挺短的.

不过运行起来效率不够,10以上的就出不来了.用位运算可以提高一点效率,这里有一个相关Blog：http://blog.csdn.net/hackbuteer1/article/details/6657109.

先记下来,貌似还有A*算法的解法.有闲心再回来做吧.

#include <iostream>
#include <cmath>
using namespace std;
int map[11][11];
int vis[11];//标志第i行x列是否放入,若放入为x,否则为-1
int n;
bool islegal(int x,int y)
{
    for(int i=0;i<x;i++)
    {
        if(vis[i]==y || (x-i== abs(y-vis[i]))) return false; //判断竖行与斜行是否已经放过皇后
    }
    return true;
}
int DFS(int d)
{
    int sum = 0;
    if(d>=n)//n行都放入了皇后
    {
        return vis[d-1]!=-1?1:0;
    }
    for(int j=0;j<n;j++)
    {
        if(islegal(d,j))
        {
            vis[d] = j;//d行j列放入皇后
            sum+=DFS(d+1);//递归下一行
            vis[d] = -1;//恢复
        }
    }

    return sum;
}
int main(int argc, const char *argv[])
{
    //freopen("output.txt","w",stdout);
    /*memset(vis,-1,sizeof(vis));
    for(int i=0;i<n;i++)
    {
        n = i;
        cout<<DFS(0)<<",";
    }*/
    int ans[11] = {1,0,0,2,10,4,40,92,352,724};
    while(cin>>n&&n)
    {
        cout<<ans[n-1]<<endl;
    }
    return 0;
}

数据小所以打表,不打表我也过不了^-^