[力扣题解]51. N皇后

devtools/2024/9/23 10:22:50/

题目:51. N皇后

思路

回溯法

代码

class Solution {
public:vector<vector<string>> result;bool right(int row, int col, int n, vector<string>& board){int i, j;// 不能同行, 这里我又没有写错,为什么结果不对呢?// `不能同行` 其实可以不需要判断for(j = 0; j < col; j++){if(board[row][j] == 'Q'){return false;}}// 不能同列for(i = 0; i < row; i++){if(board[i][col] == 'Q'){return false;}}// 不能同一斜线/* (1)\\\*/for(i = row-1, j = col-1; i >= 0 && j >= 0;i--, j--){if(board[i][j] == 'Q'){return false;}}/* (2)///*/for(i = row-1, j = col+1; i >= 0 && j < n; i--, j++){if(board[i][j] == 'Q'){return false;}}return true;}void function(int n, int row, vector<string>& board){if(row == n){result.push_back(board);return;}int i;// i : 列 for(i = 0; i < n; i++){if(right(row, i, n, board)){board[row][i] = 'Q';function(n, row+1, board);board[row][i] = '.';}}return;}vector<vector<string>> solveNQueens(int n) {result.clear();std::vector<std::string> board(n, std::string(n, '.'));function(n, 0, board);return result;}   
};

其中判断合法性的时候,“不能同行”其实可以不用写,因为这是在递归过程中,只会选取for循环里一个元素,接下来就递归到下一层去了(下一行),所以可以不用判断“不能同行”;

注意:在通常回溯法写path的地方改成了board(就改了个名字),当成二维数组来对待;
同时二位数组大小和棋盘相等,不可以像以往为了图省事故意创建一个大一点的数组(比如一般会凑整数,n=6,直接int path[10];


http://www.ppmy.cn/devtools/39674.html

相关文章

uniap之微信公众号支付

近来用uniapp开发H5的时候&#xff0c;需要接入支付&#xff0c;原来都是基于后端框架来做的&#xff0c;所以可谓是一路坑中过&#xff0c;今天整理下大致流程分享给大家。 先封装util.js&#xff0c;便于后面调用 const isWechat function(){return String(navigator.userA…

36.Docker-Dockerfile自定义镜像

镜像结构 镜像是将应用程序及其需要的系统函数库、环境、配置、依赖打包而成。 镜像是分层机构&#xff0c;每一层都是一个layer BaseImage层&#xff1a;包含基本的系统函数库、环境变量、文件系统 EntryPoint:入口&#xff0c;是镜像中应用启动的命令 其他&#xff1a;在…

PHP数值数组讲解,for循环及函数 遍历数组获取元素

源码 <?phpheader("Content-Type:text/html;Charsetutf8");//创建数值数组$arr1 array();//简化创建语法 $arr2 [];//通过索引为数组添加不同类型的元素$arr1[0] "zhangsan" ;//也可以乱序添加元素$arr1[2] 12 ;$arr1[1] true ; //true输出为1 f…

学生党性价比蓝牙耳机哪款好用?五款性价比机型盘点分享

在众多的蓝牙耳机里&#xff0c;对于许多预算不到的学生党来说&#xff0c;想要在有限的预算内挑选到一款性价比高、性能出色的蓝牙耳机&#xff0c;确实是一个不小的挑战&#xff0c;作为蓝牙耳机大户的我今天就来为大家盘点五款性价比极高的蓝牙耳机&#xff0c;帮助大家在有…

第九届“数维杯”大学生数学建模挑战赛(C题)深度剖析|建模完整过程+详细思路+代码全解析

问题1 问题1的建模过程如下&#xff1a; 设勘探区域为 D D D&#xff0c;勘探井位数量为 n n n&#xff0c;每个勘探井位的坐标为 ( x i , y i ) , i 1 , 2 , . . . , n (x_i,y_i),i1,2,...,n (xi​,yi​),i1,2,...,n。根据勘探数据&#xff0c;假设该区域内天然气水合物资源…

Vulstack红队评估(一)

文章目录 一、环境搭建1、网络拓扑2、web服务器(win7)配置3、域控&#xff08;winserver2008&#xff09;配置4、域内机器&#xff08;windows 2003&#xff09;配置5、调试网络是否通常 二、web渗透1、信息搜集2、端口扫描3、目录扫描4、弱口令5、phpmyadmin getshell日志gets…

Redis与Mysql双写一致性如何保证

前言 之前我就在面试被问到Redis与MySQL双写一致性如何保证&#xff1f;当时没答出来,回去做了复盘。下面这些引用了网络上给出的方案&#xff0c;加上了我自己的理解&#xff0c;希望对大家有帮助。 这道题其实就是在问缓存和数据库在双写场景下&#xff0c;一致性是如何保证…

仿照JDK源码写一个ArrayList实现

仿照JDK编写一个简化的ArrayList实现是一个很好的学习Java集合框架内部工作原理的方式。以下是一个简化版的ArrayList实现,它包含了基本的添加、获取、删除和大小检查功能。 public class MyArrayList<E> {private static final int DEFAULT_CAPACITY = 10;private Obj…