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;
}
全部评论

相关推荐

05-12 17:00
门头沟学院 Java
king122:你的项目描述至少要分点呀,要实习的话,你的描述可以使用什么技术,实现了什么难点,达成了哪些数字指标,这个数字指标尽量是真实的,这样面试应该会多很多,就这样自己包装一下,包装不好可以找我,我有几个大厂最近做过的实习项目也可以包装一下
点赞 评论 收藏
分享
能干的三文鱼刷了100道题:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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