洛谷 p1219 八皇后

时间：2023-03-09 02:02:40
洛谷 p1219 八皇后

刚参加完蓝桥杯 弱鸡错了好几道。。回头一看确实不难 写起来还是挺慢的

于是开始了刷题的道路

蓝桥杯又名搜索杯 暴力杯。。。于是先从dfs刷起

八皇后是很经典的dfs问题 洛谷的这道题是这样的

洛谷 p1219 八皇后

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

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。

输入输出格式

输入格式：

一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。

输出格式：

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

输入输出样例

输入样例#1： 
6
输出样例#1： 
2 4 6 1 3 5

3 6 2 5 1 4

4 1 5 2 6 3

4

弱鸡艰难的写了一个dfs 交一遍之后最后一个测试点没过 应该就是n==13的时候 本地跑了一下确实将近两秒才出来
我的判断条件：
            if(m[s][i]==)

            {

                int flag=;

                for(x=;x<n;x++)

                if(m[x][i]==)

                    {

                        flag=;

                        break;

                    }

                if(flag)

                for(y=i;y<n;y++)

                if(m[s+y-i][y]==&&(s+(y-i)<n))

                    {

                        flag=;

                        break;

                    }

                if(flag)

                for(y=;y<i;y++)

                if(m[s-(i-y)][y]==&&(s-(i-y)>=))

                    {

                        flag=;

                        break;

                    }

                if(flag)

                for(y=;y<i;y++)

                if(m[s+(i-y)][y]==&&(s+(i-y)<n))

                    {

                        flag=;

                        break;

                    }

                if(flag)

                for(y=i;y<n;y++)

                if(m[s-(y-i)][y]==&&(s-(y-i)>=))

                    flag=;

                if(flag)

                {

                    m[s][i]=;

                    f[s]=i+;

                    dfs(s+);

                    m[s][i]=;

                }

显然写的又笨又蠢。。

瞄一眼题解：

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

using namespace std;

int a[],b[],c[],d[];

int total;

int n;

int print()

{

    if(total<=)

    {

        for(int k=;k<=n;k++)

        cout<<a[k]<<" ";

        cout<<endl;

    }

    total++;

}

void queen(int i)

{

    if(i>n)

    {

        print();

        return;

    }

    else

    {

        for(int j=;j<=n;j++)//尝试可能的位置

        {

            if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))//如果没有皇后占领，执行以下程序

            {

                a[i]=j;//标记i排是第j个

                b[j]=;//宣布占领纵列

                c[i+j]=;

                d[i-j+n]=;

                //宣布占领两条对角线

                queen(i+);//进一步搜索，下一个皇后

                b[j]=;

                c[i+j]=;

                d[i-j+n]=;

                //（回到上一步）清除标记

            }

        }

    }

}

int main()

{

    cin>>n;

    queen();

    cout<<total;

    return ;

}

其中 a数组表示的是行；b数组表示的是列；c表示的是左下到右上的对角线；d表示的是左上到右下的对角线；

因为对于一个对角线来说 其中的点的i和j是有确定的关系的  所以不必挨个遍历去寻找对角线上有没有其他的皇后 直接把判断的复杂度降低到了O(1)！！

dalao确实是dalao 本弱鸡还是太菜了





相关文章