力扣--N皇后

news/2024/9/25 7:23:57/

题目:

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

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/news/1438343.html

相关文章

Docker 中常用的命令

docker ps //查看当前运行容器 docker ps -n 4 只看最近创建的4个容器 进入当前正在运行的容器 #我们通常容器都是使用后台方式运行的&#xff0c;需要进入容器&#xff0c;修改一些配置#命令docker exec -it 容器id bashShell#实例#方式二docker attach 容器ID# docker exec …

深入探索Kubernetes(K8s):容器编排的王者

在云计算和容器化技术飞速发展的今天&#xff0c;Kubernetes&#xff08;简称K8s&#xff09;已经成为容器编排领域的王者。K8s以其强大的自动化部署、扩展和管理能力&#xff0c;为开发者和运维人员提供了极大的便利。本文将详细介绍K8s的基本概念、核心组件、使用场景以及最佳…

2021 E3 算法题第一题(Max Sentence Length)

题目内容 You would like to find the sentence containing the largest number of words in some given text. The text is specified as a string S consisting of N characters: letters, spaces, dots (.), question marks (?) and exclamation marks (!).The text can be…

【GoWeb框架初探——GRPC】

1. GRPC介绍 1.1 什么是RPC RPC全程是Remote Procedure Call&#xff0c;远程过程调用。这是一种协议&#xff0c;是用来屏蔽分布式计算中的各种调用细节&#xff0c;使得你可以像是本地调用一样直接调用一个远程的函数。 调用流程 1&#xff09;客户端发送数据&#xff08;…

Pulsar Meetup 深圳 2024 会务介绍

“ Hi&#xff0c;各位热爱 Pulsar 的小伙伴们&#xff0c;Pulsar Meetup 深圳 2024 报名倒计时啦&#xff0c;快来报名。这里汇集了腾讯、华为和谙流科技等大量 Pulsar 大咖&#xff0c;干货多多&#xff0c;礼品多多&#xff0c;不容错过啊。 ” 活动介绍 由 AscentStream 谙…

.NET WinForm开放中的 窗体的 Designer.cs作用

一般窗体窗体 在资源管理器中会呈现 xxx.cs xxx.Designer.cs xxx.resx 》》》 .resx 是存放资源文件的&#xff0c;没啥好说的 xxx.cs 和 xxx.Designer.cs 都是partial类&#xff0c;而他们类名是一样的&#xff0c;所以在编译会生成一个文件。 xxx.Designer.cs 代码中有两…

MYSQL之锁机制

什么是锁机制? MySQL的锁机制是数据库中用于管理和控制对共享资源并发访问的一种机制。在多用户环境下&#xff0c;不同的用户可能同时对同一数据进行读写操作&#xff0c;如果没有适当的锁机制&#xff0c;就可能出现数据不一致或脏读等问题。 锁分类 1.从数据库的操作类型…

设计模式- 中介者模式(Mediator)

1. 概念 中介者模式&#xff08;Mediator Pattern&#xff09;&#xff0c;是一种对象行为型模式。该模式的主要目的是定义一个中介对象来封装一系列对象之间的交互&#xff0c;使原有对象之间的耦合变得松散&#xff0c;并且可以独立地改变它们之间的交互。 2. 原理结构图 抽…