力扣--N皇后

ops/2024/11/14 6:21:16/

题目:

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1:

输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:

输入:n = 1
输出:[["Q"]]

提示:

  • 1 <= n <= 9

该问题为典型的回溯问题,来看看代码吧

class Solution {
public:
void put_queen(int x,int y,vector<vector<int>>&attack)//x,y分别表示传进去的行和列,attack数组表示该行皇后可以攻击到的位置
{static const int dx[]={-1,1,0,0,-1,-1,1,1};static const int dy[]={0,0,-1,1,-1,1,-1,1};attack[x][y]=1;for(unsigned int i=1;i<attack.size();i++){for(int j=0;j<8;j++){unsigned int nx=x+i*dx[j];unsigned int ny=y+i*dy[j];if(nx>=0&&nx<attack.size()&&ny>=0&&ny<attack.size()){attack[nx][ny]=1;}}}
}
//line表示当前处理的行,n表示N皇后问题,queen数组表示皇后存储的位置,attack表示皇后攻击的位置,re表示存储N皇后的全部解法
void backtrack(int line,int n,vector<string>&queen,vector<vector<int>>&attack,vector<vector<string>>&re)
{if(line==n){re.push_back(queen);return;}for(int i=0;i<n;i++){if(attack[line][i]==0){vector<vector<int>> temp=attack;queen[line][i]='Q';put_queen(line,i,attack);backtrack(line+1,n,queen,attack,re);attack=temp;queen[line][i]='.';}}
}vector<vector<string>> solveNQueens(int n) {vector<vector<string>> re;//存储最终结果vector<vector<int>> attack;//标记皇后攻击位置vector<string>queen;//保存皇后位置for(int i=0;i<n;i++){attack.push_back((std::vector<int>()));for(int j=0;j<n;j++)attack[i].push_back(0);queen.push_back("");queen[i].append(n,'.');}backtrack(0,n,queen,attack,re);return re;}
};

这里我把题目链接贴上供各位查看

https://leetcode.cn/problems/n-queens/


http://www.ppmy.cn/ops/17405.html

相关文章

09.JAVAEE之网络初识

1.网络 单机时代 >局域网时代 >广域网时代 >移动互联网时代 1.1 局域网LAN 局域网&#xff0c;即 Local Area Network&#xff0c;简称LAN。 Local 即标识了局域网是本地&#xff0c;局部组建的一种私有网络。 局域网内的主机之间能方便的进行网络通信&#xff0…

迭代器模式:顺序访问集合对象元素的桥梁

在软件开发中&#xff0c;我们经常需要访问集合对象中的元素&#xff0c;而无需暴露其底层表示。迭代器模式&#xff08;Iterator Pattern&#xff09;是一种行为型设计模式&#xff0c;它提供了一种按顺序访问聚合对象元素的方法&#xff0c;而不依赖于对象的底层实现。这种模…

postCss基本介绍

&#x1f31f;什么是postCss&#xff1f; 我个人的理解postCss就是css界的babel&#xff0c;它提供一个过程&#xff0c;而在这个过程中&#xff0c;去干什么就是你自己的事情&#xff0c;所以很多人写插件&#xff0c;去做代码转换&#xff0c;或者兼容等等。 babel 提供过程 …

R可视化:绘制带有显著性标记的误差棒图

介绍 ggplot2绘制分组误差棒图加载R包 knitr::opts_chunk$set(message = FALSE, warning = FALSE) library(tidyverse) library(ggpubr) library(rstatix)# rm(list = ls()) options(stringsAsFactors = F) options(future.globals.maxSize = 10000 * 1024^2)Importing data …

C语言趣味代码(二)

1.珠玑妙算 1.1 介绍 《珠玑妙算》(Mastermind)是英国Invicta公司于1973年开始销售的一款益智游戏&#xff0c;据说迄今为止已经在全世界销售了5000万套。《珠玑妙算》于1974年获奖后&#xff0c;在1975年传入美国&#xff0c;1976年leslieH.Autl博士甚至还出版了一本名为The…

YOLOv8 实现车牌检测,生成可视化检测视频(20240424)

原项目源码地址&#xff1a;GitHub 我的源码地址&#xff1a;Gitee 环境搭建请参考&#xff1a;Win10 搭建 YOLOv8 运行环境&#xff08;20240423&#xff09;-CSDN博客 环境测试请参考&#xff1a;本地运行测试 YOLOv8&#xff08;20240423&#xff09;-CSDN博客 训练数据…

如何在PostgreSQL中使用索引覆盖扫描提高查询性能?

文章目录 解决方案1. 创建合适的索引2. 确保查询能够使用索引覆盖扫描3. 调整查询以利用索引覆盖扫描4. 监控和调优 示例代码1. 创建索引2. 编写查询3. 检查是否使用索引覆盖扫描4. 调整索引 总结 在PostgreSQL中&#xff0c;索引是提高查询性能的关键工具之一。索引允许数据库…

鼠标手辅助器

鼠标发生移动后 &#xff0c;静止在某位置指定时间后即可触发点击事件 支持多种点击事件&#xff0c;支持快捷键触发&#xff0c;支持自定义配置 有其他更好的思路 &#xff0c;支持有偿定制&#xff0c;留言留下联系方式&#xff0c;看到会加你 # !/usr/bin/python3 # -*- c…