redfgvfcbdf
redfgvfcbdf
2021-05-20 19:05
采纳率: 100%
浏览 28

N皇后问题求救求救求救

N皇后问题
问题描述
  给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都不在同一行、同一列或同一条对角线上,任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法?n小于等于8。
输入格式
  输入的第一行为一个整数n,表示棋盘的大小。
  接下来n行,每行n个0或1的整数,如果一个整数为1,表示对应的位置可以放皇后,如果一个整数为0,表示对应的位置不可以放皇后。
输出格式
  输出一个整数,表示总共有多少种放法。
 

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

4条回答 默认 最新

  • technologist_16
    已采纳

    这些经典的题目网上搜一下就有了

    https://blog.csdn.net/qq_43235359/article/details/90605468

    点赞 评论
  • redfgvfcbdf
    redfgvfcbdf 2021-05-20 19:15

    参考Aloof__的博客

    #include <bits/stdc++.h>

    using namespace std;
    typedef long long int ll;
    int N,cot;    //分别代表棋盘尺寸(皇后数量)和皇后可能成功摆放的结果总数
    int size[11];//数组的下标表示行,对应的值表示列
    int ans[11]; // 用于打表存放结果
    void dfs(int n)
    {
        int flag;
        if(n==N+1)  //当 最后一个皇后成功放置时返回.
        {
            cot++;   //成功的次数加一
            return ;
        }
        for(int i=1;i<=N;i++)
        {
            size[n]=i;   //代表将第一个皇后放置在第1行第i列(或者说第n个皇后)
            flag=1;      //放完之后就行标记
            for(int j=1;j<n;j++)  //这个for循环用来检测 这个皇后的位置和之前的n个皇后的位置是否冲突
            {
                if(size[j]==i||((abs(n-j))==abs(size[j]-i)))
                {
                    flag=0;
                    break;
                }
            }
            if(flag) dfs(n+1);   // 如果放置在第i列不冲突 则开始放下一个皇后   如果冲突 放在下一列继续判断
        }

    }
    int main()
    {
        for( N=1;N<=11;N++)//因为本题时间限制,所以需要先打表
        {
            cot=0;    //临时存放结果
            dfs(1);
            ans[N]=cot;  // 将结果依次放入表中
        }
        while(cin >>N)
        {
            if(!N) break;
            cout <<ans[N]<<endl;
        }
        return 0;

    ,。
    }
     

    点赞 评论
  • redfgvfcbdf
    redfgvfcbdf 2021-05-20 20:12

    ,,,

    点赞 评论
  • QA_Assistant
    有问必答小助手 2021-05-21 11:33

    您好,我是有问必答小助手,您的问题已经有小伙伴解答了,您看下是否解决,可以追评进行沟通哦~

    如果有您比较满意的答案 / 帮您提供解决思路的答案,可以点击【采纳】按钮,给回答的小伙伴一些鼓励哦~~

    ps:问答VIP仅需29元,即可享受5次/月 有问必答服务,了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632

    点赞 评论

相关推荐