n皇后

题目类型

搜索

题目描述

会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将n个皇后放在棋盘上(有n × n个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。

输入

n

输出

放置的具体方法,以及总共的方法数。

样例输入

4

样例输出

4 1 3
3 1 4 2
2

思路

搜索每一行皇后可以放的位置,具体见代码

上完整代码

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[100];//存储每一行皇后的位置 
int s(int x,int y)//判断皇后在x行的y个位置能否放置 
{
    for(int k=1;k<x;k++)//遍历x行以前的行 
    {
        if((y==a[k])||abs(a[k]-y)==abs(x-k))//判断与前面的皇后是否在同一行或同一对角线 
            return 0;
    }
    return 1;//返回1,表示此位置能放 
}
void f(int x)//计算第x行的皇后的位置 
{
    if(x==n+1)
    {
        for(int i=1;i<=n;i++)
            cout<<a[i]<<" ";//打印皇后所在每一行的位置 
        cout<<endl;
        ans++;//方案数 
        return;
    }

        for(int i=1;i<=n;i++)//遍历每一行的每一个位置 
        {
            if(s(x,i)){//如果满足条件 
                a[x]=i;//记录该行皇后的位置 
                f(x+1);//搜索下一行 
            }
        }

}
int main(){
    cin>>n;
    f(1);//从第一行开始 
    cout<<ans;
    return 0;
}
全部评论

相关推荐

长鑫存储
投递长鑫存储等公司10个岗位 >
点赞 评论 收藏
分享
程序员牛肉:主要是因为小厂的资金本来就很吃紧,所以更喜欢有实习经历的同学。来了就能上手。 而大厂因为钱多,实习生一天三四百的就不算事。所以愿意培养你,在面试的时候也就不在乎你有没有实习(除非是同级别大厂的实习。) 按照你的简历来看,同质化太严重了。项目也很烂大街。 要么换项目,要么考研。 你现在选择工作的话,前景不是很好了。
点赞 评论 收藏
分享
鬼迹人途:你去投一投尚游游戏,服务器一面,第一个图算法,做完了给你一个策略题,你给出方案他就提出低概率问题,答不上当场给你挂
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务