洛谷 1219 （八皇后）

八皇后  （DFS）

洛谷p1219

题目描述

检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这道题其实理解了很简单，就是这个点放了棋子，四条线上不再能放棋子

注意：如果横坐标是x，纵坐标是y，那么斜着的坐标就分别是y+x，y-x+n（n代表棋盘的大小，n皇后）

　　　　//如果无法理解，就画画图，自己就看出来了

我们把函数dfs的成员k看成点的横坐标

for循环里的 i 看做y坐标，直接纯dfs就可以写了

void dfs(int k)
{
    if(k==n+1)
    {
        ans++;
        if(ans<=3)
        {
            for(int i=1;i<=n;++i)
            {
                cout<<v[i]<<" ";
            }
            cout<<endl;
        }

    }
    else
    {
        for(int i=1;i<=n;++i)
        {
            if(b[i]==0&&c[i+k]==0&&d[i-k+n]==0)
            {
                a[k]=1;
                b[i]=1;
                c[i+k]=1;
                d[i-k+n]=1;
                v[k]=i;
                dfs(k+1);
                a[k]=0;
                b[i]=0;
                c[i+k]=0;
                d[i-k+n]=0;
            }
        }
    }
}

看着长，不难