dfs的经典题目---n皇后问题

忘是亡心i 2024-03-26 15:00 89阅读 0赞

> **题目链接：**  
> [843. n-皇后问题][843. n-]  
> **题目描述：**  
> ![在这里插入图片描述][2616e34d293d4c21badf7232f727c69f.png]

**dfs算法**

#include<iostream>
    #include<cstring>
    
    using namespace std;
    
    const int N=10;
    
    int n;
    char g[N][N];//存储地图
    bool dg[N * 2],udg[N * 2],col[N];//对角线，反对角线，列。
    
    void dfs(int x)
    {
        
        if(x==n)//递归的结束条件
        {
        
            for(int i=0;i<n;i++) puts(g[i]);
            puts("");
            return;
        }
    
        for(int i=0;i<n;i++)//搜索n行数据
        {
        
            if(!col[i] && !dg[x + i] && !udg[n - x + i])//如果说没有被用过
            {
        
                g[x][i]='Q';
                col[i]=dg[x+i]=udg[n-x+i]=true;
                dfs(x+1);//进一步搜索
                //回溯的过程
                col[i]=dg[x+i]=udg[n-x+i]=false;
                g[x][i]='.';
            }
        }
    }
    
    int main()
    {
        
        cin>>n;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                g[i][j]='.';
    
    
        dfs(0);//从第0行开始搜索
    
        return 0;
    }

[843. n-]: https://www.acwing.com/problem/content/845/
[2616e34d293d4c21badf7232f727c69f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6682148625c24bea8933d9a88f14ff4e.png

发表评论取消回复

表情：

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

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

相关阅读

相关【经典算法】N皇后问题

经典N皇后问题的算法。做一道经典题目，来一场思维旅行。

本是古典何须时尚/ 2024年05月25日 17:33/ 0 赞/ 115 阅读

相关 dfs的经典题目---n皇后问题

> 题目链接： > [843. n-皇后问题][843. n-] > 题目描述： > ![在这里插入图片描述][2616e34d293d4c21badf7232f7

忘是亡心i/ 2024年03月26日 15:00/ 0 赞/ 90 阅读

相关 DFS + 回溯法：N皇后问题

DFS + 回溯法：N皇后问题问题： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text

骑猪看日落/ 2023年10月06日 16:55/ 0 赞/ 77 阅读

相关 N皇后经典回溯算法

N皇后题目：给你一个N\N的棋盘，放置N个皇后，让皇后之间不攻击；攻击规则：皇后可攻击同行、同列、对角线上的所有皇后。题目分析：如果没有对角线限制，那么这道题就是一个

柔情只为你懂/ 2023年02月26日 10:25/ 0 赞/ 18 阅读

相关 AcWing | 【DFS】n-皇后问题

题目内容： > n-皇后问题是指将 n 个皇后放在 n∗n的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数n，请你输

男娘i/ 2022年12月20日 11:23/ 0 赞/ 172 阅读

相关 (模板)N 皇后问题(DFS 回溯剪枝)

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 ![0242897a3a17b699ec318bfcbeb17e3b.png

￡神魔★判官ぃ/ 2022年12月07日 15:11/ 0 赞/ 201 阅读

相关 HDU 2553 N皇后问题 (DFS)

/题意自己看，不会度娘 include <stdio.h> include <string.h> include <math.h>

短命女/ 2022年06月08日 08:41/ 0 赞/ 172 阅读

相关经典回溯算法之n皇后问题

这是来源于国际象棋的一个问题。n皇后问题要求在一个n×n格的棋盘上放置n个皇后，使得它们彼此不受攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一条斜线上的

素颜马尾好姑娘i/ 2022年06月07日 00:24/ 0 赞/ 320 阅读

相关 HDU - 2553 N皇后问题 (DFS)

N皇后问题 Problem Description 在N\N的方格棋盘放置了

超、凢脫俗/ 2022年05月19日 05:37/ 0 赞/ 198 阅读

相关 N 皇后问题

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

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