当前位置: 首页 > article >正文

算法题(102):八皇后

审题:

本题需要我们找出n*n的棋盘中,满足题目中所有位置规则的排列的总数,以及前三个排列方式的具体位置

时间复杂度分析:数据量小于25,可以允许2^n的算法

思路:

方法一:dfs暴力搜索

由于每行只能有一个棋子,所以我们可以一行一行的进行棋子排放,排放的时候注意当前位置是否满足列,主对角线,副对角线的规则。

综上,进入更深的搜索只需要知道该棋子是在哪一行插入即可

判断列是否可以插入:用bool类型的col数组来判断,初始化为false,表示该索引的列没被插入

判断主/副对角线是否可以插入:

我们需要对棋盘的对角线满足的函数关系进行判断

首先我们先给棋盘建立二维平面坐标系,行为x,列为y。不过这里直接判断函数有点难看,所以我们将坐标系进行翻转,从而得到右边的图

这里是主对角线,我们发现x-y得到的值都是一个整数,我们可以考虑用这个整数作为索引来访问bool数组,若bool数组为false则表示主对角线没有棋子,允许排列。

注意:这里的值可能为负数,所以我们可以加一个偏移量来充当索引

这是副对角线,同理可得,我们使用x+y作为索引记录副对角线是否有棋子插入,由于这里的x+y不可能等于负数,所以不用加偏移量

解题:

(1)变量创建

这里的path是用来记录排列方式的。

主对角线的线数是2n+1,副对角线数是n,不过为了统一,我们都用2*N来当他们的容量。

!!!:由于我们使用的是时间复杂度极高的dfs所以这里要尽量减少使用vector,而是使用普通数组代替vector。因为vector有很多边界检查等额外开销,但是普通数组有很多编译器都对它做了优化。

(2)主函数

(3)dfs

首先我们写出结束语句:

当每一行都插入了数据时,我们将count++,表示排列方式又多了一种,然后根据counts的值判断是否为前三个解,若是则输出path的数据

然后是排列逻辑:

先判断行,列,主副对角线是否有棋子存在,若都没有则进行bool数组状态更新,以及path的插入,然后进入dfs搜索下一行

回溯时:将状态返回,删除path的该层数据

P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷


http://www.kler.cn/a/594034.html

相关文章:

  • centos7/8/9安装dockerdocker-compose
  • 车载以太网网络测试-17【传输层-TCP】
  • 理想发布的下一代自动驾驶架构MindVLA是什么?
  • 【HarmonyOS Next之旅】基于ArkTS开发(三) -> 兼容JS的类Web开发(七) -> JS动画(二)
  • 进程地址空间(上)【Linux】
  • prompt工程
  • 【LangChain入门 4 Prompts组件】提示词追加示例 FewShotPromptTemplate和示例选择器ExampleSelector
  • docker部署dify
  • xss-labs第八、九关卡以及XSS GAME的Ok,Boomer关卡
  • uniapp中的vue组件与组件使用差异
  • 如何使用webpack预加载 CSS 中定义的资源和预加载 CSS 文件
  • 微分方程求解及推导过程
  • 微软Data Formulator:用AI重塑数据可视化的未来
  • 联想拯救者触摸板会每次开机都自动关闭、联想笔记本触摸板关闭、笔记本电脑触摸板自动关闭的解决方法
  • 解锁Python print()函数高级用法
  • Linux实现交换分区和时间同步
  • 如何通过spark history页面查看gluten是否集成成功
  • PCB画图软件PROTEL99SE学习-05画出铜箔来
  • 成都高精尖生态办公:国际数字影像产业园​
  • 巧用 VSCode 开启 Vue 开发之旅