洛谷 p1219 八皇后

佚名 5年前 (2019-03-26) 算法 1252人围观抢沙发百度已收录

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

于是开始了刷题的道路

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

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

上面的布局可以用序列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：

输出样例#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]==0)
            {
                int flag=1;
                for(x=0;x<n;x++)
                if(m[x][i]==1)
                    {
                        flag=0;
                        break;
                    }
                if(flag)
                for(y=i;y<n;y++)
                if(m[s+y-i][y]==1&&(s+(y-i)<n))
                    {
                        flag=0;
                        break;
                    }
                if(flag)
                for(y=0;y<i;y++)
                if(m[s-(i-y)][y]==1&&(s-(i-y)>=0))
                    {
                        flag=0;
                        break;
                    }
                if(flag)
                for(y=0;y<i;y++)
                if(m[s+(i-y)][y]==1&&(s+(i-y)<n))
                    {
                        flag=0;
                        break;
                    }
                if(flag)
                for(y=i;y<n;y++)
                if(m[s-(y-i)][y]==1&&(s-(y-i)>=0))
                    flag=0;
                if(flag)
                {
                    m[s][i]=1;
                    f[s]=i+1;
                    dfs(s+1);
                    m[s][i]=0;
                }

显然写的又笨又蠢。。

瞄一眼题解：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
int a[100],b[100],c[100],d[100];
int total;
int n;
int print()
{
    if(total<=2)
    {
        for(int k=1;k<=n;k++)
        cout<<a[k]<<" ";
        cout<<endl;
    }
    total++;
}
void queen(int i)
{
    if(i>n)
    {
        print();
        return;
    }
    else
    {
        for(int j=1;j<=n;j++)//尝试可能的位置
        {
            if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))//如果没有皇后占领，执行以下程序
            {
                a[i]=j;//标记i排是第j个
                b[j]=1;//宣布占领纵列
                c[i+j]=1;
                d[i-j+n]=1;
                //宣布占领两条对角线
                queen(i+1);//进一步搜索，下一个皇后
                b[j]=0;
                c[i+j]=0;
                d[i-j+n]=0;
                //（回到上一步）清除标记
            }
        }
    }
}
int main()
{    
    cin>>n;
    queen(1);
    cout<<total;
    return 0;
}