当前位置: 首页 > 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部署 证书申请 首先需要去…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...