当前位置: 首页 > news >正文

n-皇后问题(DFS)

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。

1_597ec77c49-8-queens.png

现在给定整数 n,请你输出所有的满足条件的棋子摆法。

输入格式

共一行,包含整数 n。

输出格式

每个解决方案占 n 行,每行输出一个长度为 n 的字符串,用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空,Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后,输出一个空行。

注意:行末不能有多余空格。

输出方案的顺序任意,只要不重复且没有遗漏即可。

数据范围

1≤n≤9

输入样例:

4

输出样例:

.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..

这题的难度就在于对于斜边的判定处理,解释放在代码里,这里直接给出代码

代码如下:

1.第一种方式(在看懂题意下可以知道每行只能放一个皇后,这样写代码更简单时间复杂度,推荐)

//第一种搜索方式
#include<iostream>
using namespace std;
const int N=20;
int n;
char g[N][N];
//由于国际象棋皇后的十字方向以及斜方向都能走,因此每行只能放一个皇后,定义一个行数组xiaochou,正斜线xie,反斜线fxie
bool xiaochou[N],xie[N],fxie[N];void dfs(int u)//u表示遍历到数组第u行
{if(u==n)//当遍历到第n-1行时已经进行完成,等于n直接输出{for(int i=0;i<u;i++) puts(g[i]);puts("");return;}for(int i=0;i<n;i++){if(!xiaochou[i]&&!xie[u+i]&&!fxie[n-u+i])//这里运用到一个数学知识,正对角线该点为u+i,其交叉对于的反对角线为n-u+i{g[u][i]='Q';xiaochou[i]=xie[u+i]=fxie[n-u+i]=true;dfs(u+1);xiaochou[i]=xie[u+i]=fxie[n-u+i]=false;//记得回溯g[u][i]='.';}}
}
int main()
{cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++) g[i][j]='.';}dfs(0);return 0;
}

 2.第二种方式(一个格子一个格子去枚举判断,比较容易理解,但时间复杂度要大一点)

#include<iostream>
using namespace std;
const int N=20;
int n;
char g[N][N];
//由于国际象棋皇后的十字方向以及斜方向都能走,第二种方法就是把每个格子都枚举一遍
//设置row行数组,col列数组以及两个对角线数组,来判断皇后能不能放
bool row[N],col[N],xie[N],fxie[N];void dfs(int x,int y,int s)//x和y分别表示枚举该数组到啥位置的行列坐标,s表示已经放了几个皇后
{if(y==n) y=0,x++;//每行列举完最后一列的时候,跳到下一行的第一列if(x==n){if(s==n){for(int i=0;i<n;i++) puts(g[i]);puts("");}return;}//不放皇后dfs(x,y+1,s);//放皇后if(!row[x]&&!col[y]&&!xie[x+y]&&!fxie[x-y+n]){g[x][y]='Q';row[x]=col[y]=xie[x+y]=fxie[x-y+n]=true;dfs(x,y+1,s+1);row[x]=col[y]=xie[x+y]=fxie[x-y+n]=false;g[x][y]='.';}
}
int main()
{cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++) g[i][j]='.';}dfs(0,0,0);return 0;
}

难点总结:

这题需要补充的知识点就是关于对角线如何处理的问题,这里设置正对角线数组和反对角线数组来处理,正对角线为蓝色下标从左上角开始,反对角线为绿色下标从右上角开始,这里因为只要对角线中有一个皇后剩下的都不能放,所以可以看成一个bool类型的一维数组,而难处也在于bool数组的下标应该如何设置,

对于正对角线(如下图),规律就是其对角线格子横坐标加上纵坐标相等,因此代码中为x+y,

 

对于反对角线,为x-y+n,这里加n是为了不出现负数

 

 

相关文章:

n-皇后问题(DFS)

n−皇后问题是指将 n 个皇后放在 nn 的国际象棋棋盘上&#xff0c;使得皇后不能相互攻击到&#xff0c;即任意两个皇后都不能处于同一行、同一列或同一斜线上。 现在给定整数 n&#xff0c;请你输出所有的满足条件的棋子摆法。 输入格式 共一行&#xff0c;包含整数 n。 输出…...

漏洞利用和权限提升

使用Kali Linux进行漏洞利用和权限提升是渗透测试过程中的一部分&#xff0c;用于评估系统的安全性。 漏洞利用&#xff1a; 选择目标&#xff1a; 首先&#xff0c;确定 要进行漏洞利用的目标系统。这可能是一个具有已知漏洞的应用程序、服务或操作系统。 收集信息&#xff…...

开源网安受邀参加软件供应链安全沙龙,推动企业提升安全治理能力

​8月23日下午&#xff0c;合肥软件行业软件供应链安全沙龙在中安创谷科技园举办。此次沙龙由合肥软件产业公共服务中心联合中安创谷科技园公司共同主办&#xff0c;开源网安软件供应链安全专家王晓龙、尹杰受邀参会并带来软件供应链安全方面的精彩内容分享&#xff0c;共同探讨…...

回归分析扫盲:为什么非线性模型不能直接用最优子集选择法

最近有人给我发了篇文章&#xff1a; 一个问题有一堆变量&#xff0c;我们要选取哪些变量来建模呢&#xff1f;我们来看看这篇文章是怎么做的&#xff1a; 这个方法简单来说就是&#xff1a;对于这一堆变量&#xff0c;我们每次尝试剔除其中一个变量&#xff0c;然后用剩下的变…...

单例模式简介

概念&#xff1a; 单例模式&#xff08;Singleton Pattern&#xff09;是一种创建型设计模式&#xff0c;它确保一个类只有一个实例&#xff0c;并提供全局访问点。单例模式的核心思想是限制某个类只能创建一个对象实例&#xff0c;并提供对该实例的全局访问。这样可以避免多个…...

WPF自定义命令及属性改变处理

1、项目建构 2、自定义命令 namespace WpfDemo.Base {public class MyCommand : ICommand{Action executeAction;public MyCommand(Action action){executeAction action;}public event EventHandler? CanExecuteChanged;public bool CanExecute(object? parameter){retu…...

macbook m1 docker中使用go

已经有一个centos8的镜像&#xff0c;本来打算在centos8中安装go 安装方法&#xff1a; # 1.下载go的安装包 mkdir install && cd install # 任意创建个文件夹 wget https://go.dev/dl/go1.20.2.linux-amd64.tar.gz# 2. 解压 tar -C xzf go1.20.2.linux-amd64.tar.g…...

【Hello Network】DNS协议 NAT技术 代理服务器

本篇博客简介&#xff1a;介绍DNS协议 NAT技术和代理服务器 网络各协议补充 DNSDNS背景DNS介绍DNS总结域名简介 NAT技术NAT技术背景NAT IP转换过程NAPTNAT技术缺陷NAT和代理服务器 网络协议总结应用层传输层网络层数据链路层 DNS DNS是一整套从域名映射到IP的系统 DNS背景 为…...

Android 使用模拟器模拟Linux操作系统

1. 简介 在Android手机上使用模拟器模拟ubuntu等操作系统&#xff0c;便于测试 2. 软件准备 Termux&#xff1a;是一款 Android 终端模拟器和 Linux 环境应用程序&#xff0c;无需 root 或设置即可直接运行。虽然酷安和谷歌菜市场都能下载&#xff0c;但这些渠道都很久没更新…...

机器学习基础之《分类算法(5)—朴素贝叶斯算法原理》

一、朴素贝叶斯算法 1、什么是朴素贝叶斯分类方法 之前用KNN算法&#xff0c;分类完直接有个结果&#xff0c;但是朴素贝叶斯分完之后会出现一些概率值&#xff0c;比如&#xff1a; 这六个类别&#xff0c;它都有一定的可能性 再比如&#xff0c;对文章进行分类&#xff1a;…...

# Go学习-Day6

文章目录 Go学习-Day6封装继承接口 Go学习-Day6 个人博客&#xff1a;CSDN博客 封装 类似java的类的封装&#xff0c;这里我们利用大小写和工厂模式来实现封装的功能略过 继承 相似的类具有相似的方法&#xff0c;反复绑定相同的方法&#xff0c;代码冗余&#xff0c;所以引…...

分布式 - 服务器Nginx:一小时入门系列之 HTTPS协议配置

文章目录 1. HTTPS 协议2. 生成 SSL 证书和私钥文件3. 配置 SSL 证书和私钥文件4. HTTPS 协议优化 1. HTTPS 协议 HTTPS 是一种通过计算机网络进行安全通信的协议。它是HTTP的安全版本&#xff0c;通过使用 SSL 或 TLS 协议来加密和保护数据传输。HTTPS的主要目的是确保在客户…...

探秘Linux系统性能监控神器!Linux和Python技术持续学习者必看!

引言 作为Linux运维工程师&#xff0c;我们经常需要对服务器的性能进行监控和调优。而Python作为一门强大的脚本语言&#xff0c;可以帮助我们轻松实现各种系统性能监控任务。本文将介绍几个实用的Python库和工具&#xff0c;帮助我们监控Linux系统的CPU、内存、磁盘和网络等性…...

文心一言续写太监小说《名侦探世界的巫师》

《名侦探世界的巫师》是我的童年回忆&#xff0c;总是想着续写一下&#xff0c;但是又没有时间和文笔&#xff0c;文心一言出了&#xff0c;由于目前大模型貌似可以联网&#xff0c;可以尝试搞一波~ 目录 文章1【前六个故事还能看&#xff0c;后面就是在重复】故事2【辣眼睛】…...

Solidity 合约安全,常见漏洞(第三篇)

Solidity 合约安全&#xff0c;常见漏洞&#xff08;第三篇&#xff09; ERC20 代币问题 如果你只处理受信任的 ERC20 代币&#xff0c;这些问题大多不适用。然而&#xff0c;当与任意的或部分不受信任的 ERC20 代币交互时&#xff0c;就有一些需要注意的地方。 ERC20&#…...

Linux安装Redis数据库,无需公网IP实现远程连接

文章目录 1. Linux(centos8)安装redis数据库2. 配置redis数据库3. 内网穿透3.1 安装cpolar内网穿透3.2 创建隧道映射本地端口 4. 配置固定TCP端口地址4.1 保留一个固定tcp地址4.2 配置固定TCP地址4.3 使用固定的tcp地址连接 Redis作为一款高速缓存的key value键值对的数据库,在…...

智慧政务,长远布局——AIGC引领,加速推进数字化政府建设

在人工智能、虚拟现实等领域迅猛发展且日益成熟的背景下&#xff0c;AI行业正迈向蓬勃发展的全新阶段&#xff0c;市场规模持续扩张。与此同时&#xff0c;数字服务也正在蓬勃兴起&#xff0c;新一代信息技术为数字政府构建了坚实支撑&#xff0c;重塑了政务信息化管理、业务架…...

中央处理器(CPU):组成、指令周期、数据通路、控制方式、控制器、指令流水线,补充(多处理器系统、硬件多线程)

中央处理器&#xff08;CPU&#xff0c;Central Processing Unit&#xff09;&#xff0c;计算机控制和运算的核心&#xff0c;是信息处理和程序运行的执行单元。 CPU主要功能&#xff1a;处理指令、执行操作、控制时间、处理中断、处理数据。 其中&#xff0c;处理指令、执行…...

开源微服务如何选型?Spring Cloud、Dubbo、gRPC、Istio 详细对比

作者&#xff1a;刘军 不论您是一名开发者、架构师、CTO&#xff0c; 如果您曾深度参与在微服务开发中&#xff0c;那么相信您一定有过开源微服务框架或体系选型的疑问&#xff1a;Apache Dubbo、Spring Cloud、gRPC 以及 Service Mesh 体系产品如 Istio&#xff0c;到底应该选…...

Nginx的HTTPS部署与安全性能优化

Nginx作为一款高性能的Web服务器和反向代理服务器&#xff0c;被广泛用于应用部署和负载均衡。在安全环保意识的逐渐提高下&#xff0c;HTTPS也成为现代Web应用中必不可少的一环。本篇文章将重点介绍Nginx的HTTPS部署和安全性能优化。 一、Nginx的HTTPS部署 证书申请 首先需要去…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...