力扣--回溯算法51.N皇后

思路分析:

  1. isValue函数用于判断当前位置是否可以放置皇后,通过检查当前列、左上方斜线和右上方斜线是否有皇后来确定。
  2. dfs函数采用深度优先搜索的方式,在每一行尝试放置皇后,如果当前位置合法,则递归继续尝试下一行,直到遍历完所有行。
  3. 在每次递归结束时,如果已经遍历到最后一行,将当前解法保存到结果中。
  4. 最终返回所有解法结果。

class Solution {
    vector<vector<string>> result; // 保存所有解法的结果
    // 判断在当前位置放置皇后是否合法
    bool isValue(int n, int x, int y, vector<string>& chesspath) {
        // 检查列是否有皇后
        for (int i = 0; i < x; ++i)
            if (chesspath[i][y] == 'Q')
                return false;

        // 检查左上方斜线是否有皇后
        for (int i = x, j = y; i >= 0 && j >= 0; --i, --j) {
            if (chesspath[i][j] == 'Q')
                return false;
        }

        // 检查右上方斜线是否有皇后
        for (int i = x, j = y; i >= 0 && j < n; --i, ++j) {
            if (chesspath[i][j] == 'Q')
                return false;
        }

        // 当前位置放置皇后合法
        return true;
    }

    // 使用深度优先搜索解决N皇后问题
    void dfs(int n, int x, vector<string>& chesspath) {
        // 当前行遍历完成,将结果保存
        if (x == n) {
            result.push_back(chesspath);
            return;
        }
        
        // 遍历当前行的每一列,尝试放置皇后
        for (int j = 0; j < n; ++j) {
            // 如果当前位置可以放置皇后
            if (isValue(n, x, j, chesspath)) {
                // 放置皇后
                chesspath[x][j] = 'Q';
                // 继续搜索下一行
                dfs(n, x + 1, chesspath);
                // 回溯,撤销当前位置的皇后
                chesspath[x][j] = '.';
            }
        }
    }

public:
    // 解决N皇后问题的入口函数
    vector<vector<string>> solveNQueens(int n) {
        // 初始化棋盘为全'.'
        vector<string> chesspath(n, string(n, '.'));
        // 从第0行开始搜索解法
        dfs(n, 0, chesspath);
        // 返回所有解法结果
        return result;
    }
};

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/274552.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Stable Diffusion WebUI 生成参数:高清修复/高分辨率修复(Hires.fix)

本文收录于《AI绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里。 大家好&#xff0c;我是水滴~~ 在本篇文章中&#xff0c;我们将深入探讨 Stable Diffusion WebUI 的一个引人注目的生成参数——高分辨率修复&#xff08;Hires.fix&#xff09;。我们将逐一…

web前端之不一样的下拉菜单、不选中第一个元素的样式效果、伪类排除第一个元素、符号选择器、hover、not、first、child

MENU 效果图htmlcssJShtmlcss 效果图 htmlcssJS html <nav><ul><li class"navli"><h4>HTML5</h4><ul class"ulson"><li class"lison">HTML5</li></ul></li><li class"na…

微信小程序项目实战遇到的问题

我们以学生成绩平台来作为例子。这是我们想得到的效果。 以下是完整代码&#xff1a; index.js // index.js Page({//页面的初始数据data: {hello: 欢迎进入微信小程序的编程世界,score: 80,userArray: [{name: 张三,score: [66, 77, 86, 70, 90]},{name: 李四,score: [88, 7…

使用ES检索PDF等文档的全栈方案之前端demo(end)

写在前面 通过之前的系列文章&#xff0c;整个ES搜索文件的流程与大的问题已经统统扫除了&#xff0c;既然是全栈流程&#xff0c;是不能缺少前端查询页面的&#xff0c;前端需简单实现一个用户输入查询关键词句&#xff0c;发起搜索&#xff0c;页面以表格形式展示查询的结果…

【2024.3.19练习】统计子矩阵

题目描述 题目分析 这道题一开始没有思路&#xff0c;使用蛮力枚举的方法时间复杂度为&#xff0c;显然超时。 参考题解后学会了化二维问题为一维问题&#xff0c;先使用的复杂度限制子矩阵的高度&#xff0c;再考虑列&#xff0c;这样就将子矩阵的和问题转变为了连续子序列的…

机器人离散化阻抗控制

机器人离散化阻抗控制是一种控制策略&#xff0c;它结合了阻抗控制的思想与离散化方法&#xff0c;以实现对机器人运动与外力之间动态关系的精细调节。这种控制方法旨在使机器人在与环境交互时能够表现出期望的阻抗特性&#xff0c;从而实现对接触力和位置的精确控制。 在离散…

【源码&教程】基于GAN的动漫头像生成系统

1.研究背景 我们都喜欢动漫角色&#xff0c;并试图创造我们的定制角色。然而&#xff0c;要掌握绘画技巧需要巨大的努力&#xff0c;之后我们首先有能力设计自己的角色。为了弥补这一差距&#xff0c;动画角色的自动生成提供了一个机会&#xff0c;在没有专业技能的情况下引入定…

Word为图表设置图注并在图表清单中自动生成

1如果需要自动插入题注&#xff0c;请不要自己为文件增加新的标题样式或删除自带的标题1样式 2章节大标题最好是标题1&#xff0c;2,3而不要设置标题一、二、三&#xff0c;否则图例在自动生成时会显示 图一 -1&#xff0c;调整起来会非常不方便 若实在要使用大写中文标题&…

解决由于历史原因解析tflite失败的问题

文章目录 0. 背景1. tflite 历史遗留问题2. schema3. flatbuffers 编译器3.1 安装 FlatBuffers 编译器3.2. 编译 FlatBuffers schema 文件3.3 使用生成的 Python 文件 4 问题未解决终极解决方案 写在最前面&#xff1a;解决方法是升级tensorflow版本&#xff0c;重新生成tflite…

一款非常流行的数字音乐工作站软件FL Studio for Mac 21.2.3.3586中文版新功能特色

FL Studio&#xff08;Fruity Loops&#xff09;是一款非常流行的数字音乐工作站软件&#xff0c;它可以让用户轻松地制作各种类型的音乐。前不久&#xff0c;FL Studio发布了最新的Mac版21.2.3.3586中文版&#xff0c;这个新版本的发布让广大Mac用户感到非常兴奋。 本文将介绍…

VMware的安装和Ubuntu的配置安装

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、linux是什么&#xff1f;二、基础知识虚拟机 三、安装VMware总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; Linux是一个功能…

奥特曼剧透GPT-5,将在高级推理功能上实现重大进步

奥特曼&#xff1a;“GPT-5的能力提升幅度将超乎人们的想象...” 自 Claude 3 发布以来&#xff0c;外界对 GPT-5 的期待越来越强。毕竟Claude 3已经全面超越了 GPT-4&#xff0c;成为迄今为止最强大模型。 而且距离 GPT-4 发布已经过去了整整一年时间&#xff0c;2023年3月1…

Spring Boot 自动化单元测试类的编写过程

前言 Web环境模拟测试 企业开发不仅要保障业务层与数据层的功能安全有效&#xff0c;也要保障表现层的功能正常。但是我们一般对表现层的测试都是通过postman手工测试的&#xff0c;并没有在打包过程中代码体现表现层功能被测试通过。那么能否在测试用例中对表现层进行功能测…

C#,图论与图算法,有向图(Graph)之环(Cycle)判断的颜色算法与源代码

1 检查该图是否包含循环 给定一个有向图,检查该图是否包含循环。如果给定的图形至少包含一个循环,则函数应返回true,否则返回false。 方法:深度优先遍历可用于检测图中的循环。连接图的DFS生成树。只有当图中存在后缘时,图中才存在循环。后边是从节点到自身(自循环)或…

WiFi是可以连接网络,但是在Pixel 手机上就连接提示受阻,无法上网-解决方法

1&#xff0c;通过USB连接手机&#xff0c;然后通过adb命令执行 adb shell settings delete global captive_portal_mode adb shell settings put global captive_portal_mode 0 adb shell settings get global captive_portal_mode adb shell settings delete global capti…

大数据面试题 —— HBase

目录 什么是HBase简述HBase 的数据模型HBase 的读写流程HBase 在写的过程中的region的split的时机HBase 和 HDFS 各自的使用场景HBase 的存储结构HBase 中的热现象&#xff08;数据倾斜&#xff09;是怎么产生的&#xff0c;以及解决办法有哪些HBase rowkey的设计原则HBase 的列…

[LLM] 大模型基础|预训练|有监督微调SFT | 推理

现在的大模型在进行预训练时大部分都采用了GPT的预训练任务&#xff0c;即 Next token prediction。 要理解大语言模型&#xff08;LLM&#xff09;&#xff0c;首先要理解它的本质&#xff0c;无论预训练、微调还是在推理阶段&#xff0c;核心都是next token prediction&#…

SLAM 求解IPC算法

基础知识&#xff1a;方差&#xff0c;协方差&#xff0c;协方差矩阵 方差&#xff1a;描述了一组随机变量的离散程度 方差 每个样本值 与 全部样本的平均值 相差的平方和 再求平均数&#xff0c;记作&#xff1a; 例如&#xff1a;计算数字1-5的方差&#xff0c;如下 去中心化…

.NET 异步编程(异步方法、异步委托、CancellationToken、WhenAll、yield)

文章目录 异步方法异步委托async方法缺点CancellationTokenWhenAllyield 异步方法 “异步方法”&#xff1a;用async关键字修饰的方法 异步方法的返回值一般是Task<T>&#xff0c;T是真正的返回值类型&#xff0c;Task<int>。惯例&#xff1a;异步方法名字以 Asy…

键盘映射工具KeyTweak的使用,把F9和F10改为 Home、End

如果你的笔记本没有Home、End键 对于写文字和写代码影响还是比较大的 下面使用键盘映射工具KeyTweak 把F9和F10分别改为 Home、End 然后点击ok 电脑重启后 就生效了 很好用 完美解决 小尺寸笔记本 的按键少的烦恼 可以自己再琢磨琢磨 去映射 符合自己需求的按键 软件下载链接&…
最新文章