力扣909. 蛇梯棋

news/2024/2/23 15:58:43/文章来源:https://blog.csdn.net/N_BenBird/article/details/135638071

广度优先搜索 + 动态规划

  • 思路:
    • 定义 pair {id, step} 为到达格子编号 id,使用的步数 step,记作 step[id];
    • 记录下所摇骰子 1 - 6 到达的格子编号 next,step[next] = step[id] + 1:
      • 走了 1 步,所能到达的编号;如果中途遇到传送门,直接更新 next 编号;
      • 使用一个数组记录编号是否已经被访问,如果被访问,本着使用步数最少,直接使用上次到达该位置的状态,往后摇骰子即可;
      • 编号没有被访问,则标记染色,同时更新状态 step[next];
    • 基于这些 step[id] 状态队列,广度优先搜索,动态更新状态,直到到达终点时停止;
    • 获取方格值,需要有一个编号到行列号的映射函数:
      • private:std::pair<int, int> id2rc(int id, int n) {int row = (id - 1) / n;int column = (id - 1) % n;if (row % 2 == 1) {column = n - 1 - column;}return {n - 1 - row, column};}

      • n - 1 - row 是因为起点是从左下角开始;
      • 因为是左右盘桓,奇偶行的列号发生颠倒;
class Solution {
public:int snakesAndLadders(vector<vector<int>>& board) {int n = board.size();std::vector<int> visited(n * n + 1);std::queue<std::pair<int, int>> qu;qu.emplace(1, 0);while (!qu.empty()) {auto p = qu.front();qu.pop();for (int i = 1; i <= 6; ++i) {int next = p.first + i;if (next > n *n) {break;}// update next row & columnauto rc = id2rc(next, n);// gateway and passthrough to the dstif (board[rc.first][rc.second] > 0) {next = board[rc.first][rc.second];}// final stateif (next == n * n) {return p.second + 1;}if (!visited[next]) {visited[next] = true;qu.emplace(next, p.second + 1);}}}return -1;}private:std::pair<int, int> id2rc(int id, int n) {int row = (id - 1) / n;int column = (id - 1) % n;if (row % 2 == 1) {column = n - 1 - column;}return {n - 1 - row, column};}
};

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

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

相关文章

【设计模式-03】Strategy策略模式及应用场景

一、简要描述 Java 官方文档 Overview (Java SE 18 & JDK 18)module indexhttps://docs.oracle.com/en/java/javase/18/docs/api/index.html Java中使用到的策略模式 Comparator、comparable Comparator (Java SE 18 & JDK 18)declaration: module: java.base, pa…

WPF真入门教程28--项目案例--MQTT服务器和客户端

1、先上图看帅照 这个案例还是布局加视图模型&#xff0c;样式应用&#xff0c;业务逻辑&#xff0c;该项目是一个mqtt服务器和客户端的通信工具&#xff0c;这里不去分析mqtt的通信原理&#xff0c;关注在于wpf技能的应用&#xff0c;能够掌握这个例子&#xff0c;离项目开发…

C#编程-在线程中使用同步

在线程中使用同步 在线程应用程序中,线程需要相互共享数据。但是,应用程序应该确保一个线程不更改另一个线程使用的数据。考虑有两个线程的场景。一个线程从文件读取工资,另一个线程尝试更新工资。当两个线程同时工作时,数据就会受损。下图显示了两个线程同时访问一个文件…

杨中科 .NETCORE EFCORE第七部分 一对一,多对多

一对一 一对一关系配置 1、builder.HasOne(o >o.Delivery).WithOne(d>d.Order).HasForeignKey(d>dOrderId); 2、测试插入和获取数据 示例 新建 Order 新建 Delivery DeliveryConfig OrderConfig 执行 迁移命令 查看数据库 测试数据插入 运行查看数据 多对多…

Python文件自动化处理

os模块 Python标准库和操作系统有关的操作创建、移动、复制文件和文件夹文件路径和名称处理 路径的操作 获取当前Python程序运行路径不同操作系统之间路径的表示方式 windows中采用反斜杠(\)作为文件夹之间的分隔符 Mac和Linux中采用斜杠(/)作为文件夹之间的分隔符 把文件…

Qt优秀开源项目之二十一:遇见QSkinny,一个轻量级Qt UI库

目录 一.QSkinny简介 二.工作原理 三.编译 一.QSkinny简介 QSkinny库基于Qt Graphic View和Qt/Quick中少量的核心类。它提供了一组轻量级控件&#xff0c;可以在C或QML中使用这些控件。QSkinny默认是启用硬件加速的&#xff0c;非常适合嵌入式设备&#xff0c;目前已经应用于…

[DL]深度学习_Feature Pyramid Network

FPN结构详解 目录 一、概念介绍 二、结构详解 1、对比试验 2、特征图融合 3、结构详解 4、不同尺度预测 5、Proposal映射到预测特征层 一、概念介绍 Feature Pyramid Network (FPN)是一种用于目标检测和语义分割的神经网络架构。它的目标是解决在处理不同尺度的图像时…

SQLServer 为角色开视图SELECT权限,报错提示需要开基础表权限

问题&#xff1a; 创建了个视图V&#xff0c;里面包含V库的a表&#xff0c;和T库的b表 为角色开启视图V的SELECT权限&#xff0c;提示T库的b表无SELECT权限&#xff0c;报错如下 解决方案&#xff1a; ①在T库建个视图TV&#xff0c;里面包含b表&#xff08;注意是在b表的对…

基于SSM的戏剧推广网站的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue、HTML 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是…

使用串口 DMA 模式接收不定长数据

一、简介 曾经遇到客户有一个需求&#xff0c;需要用串口 DMA 的方式接收不定长度的数据&#xff0c;DMA 有个缺点就是在每次传输前需要设定好传输的字节长度&#xff0c;这种方式显然对于接收不定长度的数据来说没有那么灵活。但 DMA 也有着显著的优点&#xff0c;如可直接访…

Linux环境搭建FastDFS文件服务器(附带Nginx安装)

本文主要介绍在linux服务器如何搭建FastDFS文件服务器。大概分为9个步骤&#xff0c;由于内容较为繁琐。下面带你入坑&#xff01; 首先简单介绍一下FastDFS是淘宝资深架构师余庆老师主导开源的一个分布式文件系统&#xff0c;用C语言编写。适应与中小企业&#xff0c;对文件不…

电脑安装 Python提示“api-ms-win-crt-process-l1-1-0.dll文件丢失,程序无法启动”,快速修复方法,完美解决

在windows 10系统安装完python后&#xff0c;启动的时候&#xff0c;Windows会弹出错误提示框“无法启动此程序&#xff0c;因为计算机中丢失了api-ms-win-crt-process-l1-1-0.dll&#xff0c;尝试重新安装该程序以解决此问题。” api-ms-win-crt-process-l1-1-0.dll是一个动态…

网络层协议及IP编址与IP路由基础华为ICT网络赛道

目录 4.网络层协议及IP编址 4.1.网络层协议 4.2.IPv4地址介绍 4.3.子网划分 4.4.ICMP协议 4.5.IPv4地址配置及基本应用 5.IP路由基础 5.1.路由概述 5.2.静态路由 5.3.动态路由 5.4.路由高阶特性 4.网络层协议及IP编址 4.1.网络层协议 IPv4(Internet Protocol Versi…

C语言——编译和链接

&#xff08;图片由AI生成&#xff09; 0.前言 C语言是最受欢迎的编程语言之一&#xff0c;以其接近硬件的能力和高效性而闻名。理解C语言的编译和链接过程对于深入了解其运行原理至关重要。本文将详细介绍C语言的翻译环境和运行环境&#xff0c;重点关注编译和链接的各个阶段…

基于JavaWeb+BS架构+SpringBoot+Vue+Hadoop短视频流量数据分析与可视化系统的设计和实现

基于JavaWebBS架构SpringBootVueHadoop短视频流量数据分析与可视化系统的设计和实现 文末获取源码Lun文目录前言主要技术系统设计功能截图订阅经典源码专栏Java项目精品实战案例《500套》 源码获取 文末获取源码 Lun文目录 目  录 目  录 I 1绪 论 1 1.1开发背景 1 1.2开…

【国内访问github不稳定】可以尝试fastgithub解决这个问题

1、下载 https://github.com/dotnetcore/FastGithub https://github.com/dotnetcore/FastGithub/releases 官网下载即可&#xff0c;比如&#xff0c;我用的是这个&#xff1a;fastgithub_osx-x64.zip&#xff08;点这里下载&#xff09; 2、安装 如下图双击启动即可 3、…

大模型开启应用时代 数钉科技一锤定音

叮叮叮叮&#xff01;数钉智造大模型&#xff0c;“定音”强势发布&#xff01; 随着科技的飞速发展&#xff0c;大模型技术已逐渐成为推动产业变革的核心力量。在这一浪潮中&#xff0c;数钉科技凭借深厚的技术积累和敏锐的市场洞察力&#xff0c;成功利用大模型技术搭建起智能…

SSL之mkcert构建本地自签名

文章目录 1. 什么是SSL2. mkcert&#xff1a;快速生成自签名证书2.1 mkcert的工作流程如下&#xff1a;2.2 window 本地实现自签证书2.2.1 下载安装2.2.2 下载,生成本地 SSL2.2.3 生成 pem 自签证书,可供局域网内使用其他主机访问。2.2.4 使用-psck12 生成*.p12 文件 2.3 Sprin…

盲盒小程序搭建:为盲盒企业、创业者提供新的机遇

近年来&#xff0c;盲盒因其不确定性以及拆盲盒带来的惊喜感&#xff0c;受到了广大消费者的追捧&#xff01;盲盒是由各类手办等组成的&#xff0c;玩家能够以低价格拆到性价比高的盲盒商品&#xff0c;这种购物体验激发了玩家的购物乐趣&#xff0c;因此&#xff0c;盲盒行业…

植物大战僵尸-C语言搭建童年游戏(easyx)

游戏索引 游戏名称&#xff1a;植物大战僵尸 游戏介绍&#xff1a; 本游戏是在B站博主<程序员Rock>的视频指导下完成 想学的更详细的小伙伴可以移步到<程序员Rock>视频 语言项目&#xff1a;完整版植物大战僵尸&#xff01;可能是B站最好的植物大战僵尸教程了&…