经典算法 青蛙跳杯子
青蛙跳杯子
题目描述
桌子上有n行m列的杯子，每个杯子与相邻杯子之间的距离为1，已知青蛙的跳跃半径为d，青蛙现在在第一行第一列的杯子上，它跳到最后一行最后一列的杯子上，最少需要跳几次？
输入描述
输入只有一行，分别为整数n, m和实数d。
输出描述
直接输出青蛙跳的最小步数。
输入示例
3 4 1.5
输出示例
3
样例解释
，表示青蛙的一条可能路径，只要再跳3步就行。
，。。。
。，。。
。。，，
c++代码(暴力bfs) 大约O(m * n * d)
#include<bits/stdc++.h>using namespace std;int n, m, ans = INT_MAX;
double d;
vector<vector<int>> dp;class node{
public:int i, j, recoder;
};void bfs() {dp[0][0] = 0;queue<node> q;node k, w;k.i = 0, k.j = 0;q.push(k);while(!q.empty()) {k = q.front(), q.pop();for (int i = 0; i <= (int)(d) && k.i + i < n; i++) {for (int j = 0; j <= (int)(d) && k.j + j < m && i * i + j * j <= d * d; j++) {if (dp[k.i][k.j] + 1 < dp[k.i + i][k.j + j]) {w.i = k.i + i, w.j = k.j + j;dp[w.i][w.j] = dp[k.i][k.j] + 1;q.push(w);}}}}
}int main() {cin >> n >> m >> d;dp = vector<vector<int>>(n, vector<int>(m, INT_MAX));bfs();cout << dp[n - 1][m - 1];return 0;
}
c++代码(贪心法) 大约等于O(min(m, n) * d)
#include<bits/stdc++.h>using namespace std;int n, m, x, y, cont = 0, a, b;
double d, z;int main() {cin >> n >> m >> d;a = 0, b = 0;while(a != n - 1 || b != m - 1) {z = DBL_MAX;for (int i = 0; i <= (int)(d) && a + i < n; i++) {for (int j = 0; j <= (int)(d) && b + j < m && i * i + j * j <= d * d; j++) {int delta = (n - 1 - (a + i)) * (n - 1 - (a + i)) + (m - 1 - (b + j)) * (m - 1 - (b + j));if (delta < z) z = delta, x = a + i, y = b + j;}}a = x, b = y;cont++;}cout << cont;return 0;
}//by wqs
题目解析
暴力法
暴力法的思路很简单，我们定义dp[i][j]表示从(0, 0)到(i, j)最少需要多少步
从队列取出dp[i][j]
遍历dp[i ~ i + int(d)][j ~ j + int[d]]如果两点距离小于d则更新
dp[i ~ i + int(d)][j ~ j + int[d]] = min(dp[i ~ i + int(d)][j ~ j + int[d]], dp[i][j] + 1);
然后把dp[i ~ i + int(d)][j ~ j + int[d]]加入队列，
循环这个步骤就行。
贪心法
贪心法的思路是我们没必要将所有状态加入队列。
我们只需要把与终点直线距离最小的那个点加入就行了。
怎么证明我不会，自己去搜搜吧。
事实上，有一种情况是有2个点同时距离终点最小。
因为这些坐标都是整数，所以这两个状态是对称的你只要选择其中一个就好了。
也因为这些坐标都是整数，实际上不可能会出现3个点或者更多点了。
因为每次只加入一个点，所以干脆可以把队列改成循环了。循环末尾改变下状态就行。
相关文章：
经典算法 青蛙跳杯子
青蛙跳杯子 题目描述 桌子上有n行m列的杯子，每个杯子与相邻杯子之间的距离为1，已知青蛙的跳跃半径为d，青蛙现在在第一行第一列的杯子上，它跳到最后一行最后一列的杯子上，最少需要跳几次？ 输入描述 输入…...
C语言-函数的递归和迭代
以下是我初学C语言的笔记记录，欢迎在评论区补充留言 一，函数的递归 大致有这么几个问题【我看完这堂课后，自己总结的几个问题】 * 问题 1，什么是函数的递归, 2，它是干什么用的，3，有什么条件吗…...
Linux安装部署Postgresql数据库
联网安装方案 Linux能在线安装依赖组件的前提下，可以快速安装部署PG数据库，安装过程使用root管理员帐号： 首先，使用如下命令自动下载Postgresql组件： # 在openEuler、Fedora或CentOS 8上，你可能会使用&a…...
学习与规划的融合Dyna-Q:python从零实现
🧠 向所有学习者致敬！ “学习不是装满一桶水，而是点燃一把火。” —— 叶芝 我的博客主页： https://lizheng.blog.csdn.net 🌐 欢迎点击加入AI人工智能社区！ 🚀 让我们一起努力，共创…...
电子病历高质量语料库构建方法与架构项目（环境聆听与自动化文档生成篇）
电子病历高质量语料库的构建是一个复杂而系统的工程，涉及数据收集、清洗、标注、验证等多个环节。在项目实施过程中，"环境聆听"和"自动化文档生成"是两个关键支撑要素，前者确保项目能够适应不断变化的技术和业务环境，后者则保障项目过程的可追溯性和知…...
LegalOne：本土与国际视野融合的法律评级，大湾区律师及律师事务所榜单申报启动
在广东这片法律服务发展的热土上，从1979年全国首家法律服务机构诞生，到如今培育出4700家律所与8.7万律师，法律行业始终蓬勃向前。随着粤港澳大湾区建设推进，法律服务市场迈向双向融合的国际化新阶段，众多优秀律所和律师…...
突破传统！TTRL如何开启大模型无监督强化学习新篇章？
在大语言模型（LLMs）蓬勃发展的时代，如何让模型在无明确标签数据下有效学习成为关键难题。本文提出的Test-Time Reinforcement Learning（TTRL）给出了创新解法。它利用多数投票估计奖励，实现LLMs自我进化&…...
什么是：云边端一体化架构
什么是云边端一体化架构 文章目录 什么是云边端一体化架构云、边、端云计算边缘计算终端设备 云边端一体化协同云边端一体化架构协同的流程云边端一体化架构协同的应用云边端一体化架构协同的价值云边端一体化架构协同未来发展趋势 云、边、端 云（Cloud）…...
【2025域适应科研日报】
本笔记主要为了记录自己的科研日报，前段时间刚开始想写的初衷也是为了自己的思考不跑偏，但是有几天又没有坚持下来，看到一位学长的文章，发现这种形式还是很有必要的，所以自己也打算坚持记录下来，由于还正在…...
Linux从入门到精通：全面掌握基础命令与高效操作实战指南
引言 Linux 作为开发者、运维工程师及技术爱好者的核心工具，其命令行的高效性与灵活性无可替代。但对于新手而言，复杂的命令与文件结构往往令人困惑。本文基于官方文档与实践经验，系统梳理 Linux 基础命令、文件管理、目录操作、高级技巧 四大…...
如何提升个人的稳定性？
提升自我的稳定性是一个系统性工程，需要从内在认知、情绪管理、行为习惯到外在环境等多个维度进行优化。 以下是一些具体建议，帮助你逐步增强内心的稳定感： 一、内在认知调整 1. 建立清晰的自我认知 通过反思（如写日记、冥想…...
电机常用易混淆概念说明（伺服、舵机、多轮）
1. 概述 基础动力需求 ：普通电机（如水泵、风扇）。 高精度控制 ：优先伺服系统或伺服电机（如数控机床）。 微型化场景 ：舵机（如遥控模型）。 移动底盘 ：单舵轮成…...
短视频矩阵系统：源码搭建与定制化开发的深度剖析
在短视频行业蓬勃发展的当下，越来越多的企业和个人希望构建自己的短视频矩阵系统。而在搭建过程中，源码搭建和定制化开发是两种常见的选择，它们各有优劣，适用于不同的需求场景。本文将从多个维度深入探讨两者的区别，为…...
8.进程概念（四）
一、环境变量 1.基本概念 环境变量(environment variables)⼀般是指在操作系统中用来指定操作系统运行环境的⼀些参数。 如：我们在编写C/C代码的时候，在链接的时候，从来不知道我们的所链接的动态静态库在哪里，但是照样可以链接成…...
Windows服务器提权实战：常见方法、场景与防御指南
在渗透测试中，权限提升（提权）是从低权限账户（如IIS、Apache运行账户）获取系统管理员（如SYSTEM）权限的关键步骤。本文将从实战角度解析Windows服务器提权的常见技术，并结合真…...
 ----顶点指定和基本图元的绘制)
OpenGL-ES 学习(14) ----顶点指定和基本图元的绘制
目录 本节概述顶点的指定常量顶点属性和顶点数组顶点数组顶点属性的定义Shader 中声明顶点属性变量顶点属性的绑定 基本图元绘制基本图元三角形直线绘制图元的API 本节概述 绘制图形的第一步就是指定顶点坐标，可以每个顶点指定，也可以是用于所有顶点的常…...
spring-cloud-alibaba最新版本聚合项目创建
1. 创建聚合项目 修改 pom.xml spring-boot 当前最新版本是 3.4.5 但是 spring-cloud-alibaba 的最新版本是 2023.0.3.2，只适配到 spring-boot 3.2.4 还没有适配到 spring-boot 的 3.4.5 版本。 pom.xml 文件内容如下(可以直接复制)： <?xml vers…...
网络分析/
三、网络分析（Network Analysis） 网络分析用于解决路径规划、资源分配等问题，广泛应用于交通规划、物流配送、紧急救援等领域。ArcPy 提供了强大的网络分析工具，如 MakeNetworkDataset、Solve 等。 （一）使用…...
Flutter PIP 插件 ---- 新增PipActivity，Android 11以下支持自动进入PIP Mode
接上文 Flutter PIP 插件 ---- Android 项目地址 PIP， pub.dev也已经同步发布 pip 0.0.3，你的加星和点赞，将是我继续改进最大的动力 开发文档 Add videos using picture-in-picture (PiP)介绍PIP功能从 Android 8.0 (API level 26) 引入&…...
权限提升—Linux提权内核溢出漏洞辅助项目
前言 今天开启Linux提权的篇章，主要是讲一下Linux的内核漏洞提权，利用方式和Windows系统漏洞提权差不多，也是网上的项目扫一下，然后根据漏洞编号去找exp即可。 信息收集 首先要说一下Linux用户的权限划分。 系统用户ÿ…...
超稳定性理论
为了更好的理解后面如何利用超稳定性理论来设计MRACS，本篇先对超稳定性理论做一个介绍。 1、理论介绍 在超稳定性理论中，核心的系统结构如下： 其包含一个线性的前向回路 G ( s ) G(s) G(s)和一个非线性的反馈回路 φ ( v ) \varphi (v) φ…...
治理和管理的区别
治理（Governance）与管理（Management）是两个在组织和社会运行中经常被提及的概念，它们虽然在某些方面有相似之处，但在内涵、范围、主体和目标等方面存在显著的区别。以下是它们的主要区别： 一、…...
业务流程BPM能力框架体系及华为中兴流程变革案例P83（83页PPT）（文末有下载方式）
资料解读：《业务流程 BPM 能力框架体系及华为中兴流程变革案例》 详细资料请看本解读文章的最后内容。 该文档围绕业务流程管理（BPM）能力框架体系展开，先阐述其定义、驱动因素与能力框架，再详细介绍战略规划、流程治理…...
如何通过日志在本地调试LangChain编写的程序？
LangSmith可以记录LangChain程序对LLM的调用，但它需要登陆LangSmith网站才能看到。有什么办法在本地就能看到详细的信息，以方便调试LangChain编写的程序吗？ 使用LangChain提供的set_debug(True) 在Python代码中只需要导入set_debug这个方法…...
UE实用地编插件Physical Layout Tool
免费插件 https://www.fab.com/zh-cn/listings/a7fb6fcf-596f-48e9-83cc-f584aea316b1 可以通过物理模拟批量放置物体 不用再一个个摆放了 装饰环境从未如此简单，您不必再考虑对齐物体。 物理地放置物体，移动它们，在移动或在地图上放置物体…...
传感器的精度，灵敏度等概念介绍
文章目录 🏔️ 海拔高度传感器的四个核心指标1. 🎯 **精度（Accuracy）——“测得的高度准不准”**2. ⚡ **灵敏度（Sensitivity）——“高度微小变化有没有反应”**3. 🔍 **分辨率（Reso…...
前端八股 CSS 1
盒子模型 进行布局时将所有元素表示为一个个盒子box padding margin border content content：盒子内容 待显示的文本和图像 padding：内边距，内容和border之间的空间，不能为负数，受bkc影响 border:边框，…...
Transformer架构的解耦重组现象
技术演进图谱与技术成熟度曲线 （一）架构创新范式迭代 1.1 Transformer架构的解耦重组现象 以2025年Opt模型为例，其通过引入强化学习微调模块实现了传统单层堆叠架构向"感知-推理分离"模式的转型。实验数据显示，该架构…...
【Android】四大组件
目录 1. Activity 2. Service 3. BroadcastReceiver 4. ContentProvider 四大组件各自承担着不同的职责，彼此之间协同工作，共同为用户提供一个流畅的APP体验。 1. Activity 负责展示用户界面，就像App的一个个“页面”，用户通…...
贪心算法精解（Java实现）：从理论到实战
一、贪心算法概述 贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优决策的算法策略。它通过局部最优选择来达到全局最优解，具有高效、简洁的特点。 核心特点： 局部最优选择：每一步都做出当前看…...
基于BERT类的MRPC语义相似度检测（从0到-1系列）
基于BERT类的MRPC语义相似度检测（从0到-1系列） 介绍 BERT（Bidirectional Encoder Representations from Transformers）是由Google开发的一种预训练模型，它是一种基于Transformer机制的深度双向模型，可以对…...
mysql-窗口函数一
目录 一、感受一下分组与窗口函数的区别 二、滑动窗口（子窗口）大小的确认 2.1 分组函数下order by使用 2.2 窗口子句 2.3 执行流程 三、函数使用 窗口函数需要mysql的版本大于等于8才行，可以先检查一下自己的mysql版本是多少 select ve…...
HashMap，高效 哈希
java HashMap 有独特的设计。 哈希表数组的每个位置是一个哈希桶，里面由链表或红黑树实现。（> 8 或 < 6 的变化时，避免频繁切换） 容量（capacity）： 哈希表中桶（bucket…...
PyTorch入门------训练图像分类器
前言 1. 操作步骤 2. 数据集 一、公共部分 1.加载并归一化 CIFAR10 2.定义卷积神经网络 二、训练、保存模型参数部分 train_and_save.py 3.定义损失函数和优化器 4.训练网络(使用 CPU 或者 GPU) 5.保存训练好的模型参数 三、加载模型参数、模型推理部分 load_and_infer.py 6…...
DeepSeek V3 架构创新：大规模MoE与辅助损失移除
DeepSeek 团队推出的全新 DeepSeek V3 模型版本，相比之前的 V2 版本，V3 的参数量从两千多亿一跃攀升到 6710 亿，近乎实现了参数规模的三倍增长。如此宏大的模型规模并不只是简单地堆砌参数，而是建立在稀疏混合专家（Mixture-of-Experts，MoE）结构之上。得益于 MoE 的稀疏激…...
MCP 多工具协作链路设计：打造真正的智能工作流
目录 [TOC] 🚀 MCP 多工具协作链路设计：打造真正的智能工作流 🌟 多工具协作链核心思想 🛠️ 设计示例：智能文档分析系统 📑 1. MCP Server 定义多工具 list_txt_files.py read_file_content.py su…...
某修改版软件，已突破限制！
聊一聊 现在很多输入法都带有广告。 用着用着，不是提示升级就是弹出资讯。 特别是忙的时候，很影响心情。 今天给大家分享一款干净的输入法软件。 希望能你喜欢。 软件介绍 Q拼音输入法 工具我们下载后，进行安装。 双击打开，…...
透视Linux内核：深度剖析Socket机制的本质
在Linux操作系统构建的网络世界里，Socket 宛如纵横交错的交通枢纽，承担着不同应用程序间数据往来的重任。无论是日常浏览网页时，浏览器与 Web 服务器间信息的快速交互；还是畅玩网络游戏过程中，玩家操作指令与游戏服务器…...
PostgreSQL数据表操作SQL
数据表操作 创建表 CREATE TABLE t_test(id SERIAL PRIMARY KEY,name varchar(30),birthday date);修改表名 ALTER TABLE t_test RENAME TO t_test1;添加列 ALTER TABLE t_test1 ADD COLUMN score numeric(5,2);删除列 ALTER TABLE t_test1 DROP COLUMN score;修改数据类型 AL…...
OpenAI最新发布的GPT-4.1系列模型，性能体验如何？
简单来说，这次GPT-4.1的核心思路就是：更实用、更懂开发者、更便宜！OpenAI这次没搞太多花里胡哨的概念，而是实实在在地提升了大家最关心的几个点：写代码、听指令、处理超长文本，而且知识库也更新到了2024年6月。 写代码。要说这次GPT-4.1最亮眼的地方，可能就是写代码这块…...
2025五一数学建模C题完整分析论文（共36页）（含模型、可运行代码、数据）
2025年五一数学建模C题完整分析论文 摘要 一、问题分析 二、问题重述 三、模型假设 四、符号定义 五、 模型建立与求解 5.1问题1 5.1.1问题1思路分析 5.1.2问题1模型建立 5.1.3问题1代码 5.1.4问题1求解结果 5.2问题2 5.2.1问题2思路分析 5.2.2问题…...
Vue2基础速成
一、准备工作 首先下载vue2的JavaScript库，并且命名为vue.min.js 下载链接：https://cdn.jsdelivr.net/npm/vue2（若链接失效可去vue官网寻找） CTRLS即可下载保存 文件目录结构 二、使用操作原生DOM与使用VUE操作DOM的便捷性比较…...
Java大厂硬核面试：Flink流处理容错、Pomelo JVM调优、MyBatis二级缓存穿透防护与Kubernetes服务网格实战解析
第二幕：系统架构设计 面试官：设计一个处理10万QPS的秒杀系统需要的技术方案和技术选型 xbhog：采用基础架构： 存储层：Redis限流分布式锁服务层：Sentinel流量控制消息层：RocketMQ事务消息保证最…...
Python实现简易博客系统
下面我将介绍如何使用Python实现一个简易的博客系统，包含前后端完整功能。这个系统将使用Flask作为Web框架，SQLite作为数据库，并包含用户认证、文章发布、评论等基本功能。 1. 系统架构设计 技术栈选择 后端：Flask (Python Web框架)数据库：SQLite (轻量…...
【T型三电平仿真】SPWM调制
自然采样法和规则采样法的特点和计算 https://blog.csdn.net/u010632165/article/details/110889621 单极性和双极性的单双体现在什么地方 单极性和双极性的单双是指载波三角波的极性 为什么simulink进行电路仿真时，都需要放置一个powergui模块 任何使用SimPow…...
Astral Ascent 星界战士（星座上升） [DLC 解锁] [Steam] [Windows SteamOS macOS]
Astral Ascent 星界战士（星座上升） [DLC 解锁] [Steam] [Windows & SteamOS & macOS] 需要有游戏正版基础本体，安装路径不能带有中文，或其它非常规拉丁字符； DLC 版本 至最新全部 DLC 后续可能无法及时更新文章…...
Ubuntu20.04如何优雅的安装ROS 1（胎教级教程）
1、USTC的源： sudo sh -c . /etc/lsb-release && echo "deb http://mirrors.ustc.edu.cn/ros/ubuntu/ lsb_release -cs main" > /etc/apt/sources.list.d/ros-latest.list2、设置的ROS源添加密钥： sudo apt-key adv --keyserver …...
terraform生成随机密码
在 Terraform 中生成安全随机密码可以通过 random_password 资源实现，以下是完整实现方案及安全实践： 基础实现 (生成随机密码) terraform {required_providers {random {source "hashicorp/random"version "~> 3.5.1" # 使…...
一个linux系统电脑，一个windows电脑，怎么实现某一个文件夹共享
下载Samba linux主机名字不能超过15个字符 sudo dnf install samba samba-client -y 创建共享文件夹 sudo mkdir /shared 配置文件 vim /etc/samba/smb.conf [shared] path /shared available yes valid users linux电脑用户 read only no browsable yes p…...
等保系列（一）：网络安全等级保护介绍
一、基本概念 网络安全等级保护（以下简称：等保）是根据《中华人民共和国网络安全法》及配套规定（如《信息安全技术 网络安全等级保护基本要求》等）建立的系统性安全防护机制，要求网络运营者根据信息系统的重…...