深度优先搜索--N皇后问题

向右看齐 2022-06-08 03:59 109阅读 0赞

### 在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后，任何2个皇后不妨在同一行或同一列或同一斜线上。 ###

/*
    作者:yyfyyf1994
    题目:p1295 N皇后问题
    */
    
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    int n;
    int ans=0;
    bool a[20];
    bool x1[20];
    bool y1[20];
    void dfs(int x)
    {
        if (x>n)
        {
            ans++;
            return;
        }
        for (int i=1; i<=n; i++)
        {
            if (x1[i+x]==false&&y1[i-x+n]==false&&a[i]==false)
            {
                x1[x+i]=true;
                y1[i-x+n]=true;
                a[i]=true;
                dfs(x+1);
                a[i]=false;
                x1[x+i]=false;
                y1[i-x+n]=false;
            }
        }
    }
    int main()
    {
        scanf ("%d",&n);
        memset(a,false,sizeof(a));
        memset(x1,false,sizeof(x1));
        memset(y1,false,sizeof(y1));
        dfs(1);
        printf ("%d",ans);
        return 0;
    }

ps:以前上学的时候刷的,放上来充实一下博客内容 ![敲打][knock.gif]

[knock.gif]: /images/20220608/97d7ccc79c84481082a998f649b24c6a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，109人围观）

还没有评论，来说两句吧...

相关阅读

相关八皇后问题与其深度优先搜索 (DFS) 解法

八皇后问题与其深度优先搜索 (DFS) 解法题目背景: 八皇后问题是一个古老而经典的问题。在一个 8x8 的棋盘上，你要放置 8 个皇后，使得这些皇后之间互不攻击。这

超、凢脫俗/ 2024年02月20日 08:47/ 0 赞/ 44 阅读

相关 DFS（深度优先搜索）---城堡问题

题目描述： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9n

野性酷女/ 2023年06月25日 12:27/ 0 赞/ 55 阅读

相关深度优先搜索与广度优先搜索

算法是作用于具体数据结构之上的，深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构的。这是因为，图这种数据结构的表达能力很强，大部分涉及搜索的场景都可以抽象成“图”。

╰半橙微兮°/ 2022年10月19日 08:08/ 0 赞/ 288 阅读

相关 n皇后问题

目前会的一种解决n皇后的方法，在笔记本上大概能解除10以内的问题，更大规模的还要再去学习其他的人的好方法 include<iostream> usi

曾经终败给现在/ 2022年08月20日 06:24/ 0 赞/ 210 阅读

相关 n皇后问题

n皇后问题 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述在n×n 格的棋盘上放置

小鱼儿/ 2022年08月18日 02:30/ 0 赞/ 201 阅读

相关深度优先搜索DFS（迷宫问题）

问题及代码：给出迷宫的图纸和初始终点位置，用DFS求最小步数。 include <iostream> using namespace std; i

r囧r小猫/ 2022年07月28日 04:10/ 0 赞/ 175 阅读

相关广度优先搜索与深度优先搜索

广度优先搜索使用的是步步为营的策略，每执行一步循环就会把所有可能的情况加入队列，直到调出循环。适用于求最短的问题。深度优先搜索则是依次遍历每一种情况，直至找到问题的解。

落日映苍穹つ/ 2022年07月16日 06:43/ 0 赞/ 264 阅读

相关深度优先搜索与广度优先搜索

[二叉树深度优先遍历和广度优先遍历][Link 1] ![805461-20160514164458359-1600906940.png][] 　　对于一颗二叉树，深度

迈不过友情╰/ 2022年06月09日 07:57/ 0 赞/ 291 阅读

相关深度优先搜索--N皇后问题

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后，任何2个皇

向右看齐/ 2022年06月08日 03:59/ 0 赞/ 110 阅读

相关 N 皇后问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包

喜欢ヅ旅行/ 2022年05月17日 04:52/ 0 赞/ 234 阅读