当前位置：首页 > news >正文

每日c/c++题备战蓝桥杯(P1002 [NOIP 2002 普及组] 过河卒)

news 来源：原创 2025/7/27 17:39:50

洛谷P1002 [NOIP 2002 普及组] 过河卒题解

题目描述

过河卒是一道经典的动态规划题目。题目大意是：一个卒子从棋盘左上角(0,0)出发，要走到右下角(n,m)，棋盘上有一个马在(x,y)位置，卒子不能经过马所在位置及其周围8个位置。求卒子的合法路径总数。

解题思路

1. 问题分析

棋盘范围：棋盘为(n+1)×(m+1)的网格（坐标从0开始）
移动规则：卒子只能向右或向下移动
阻挡条件：马的位置及其控制的8个位置不可达
核心目标：统计从起点到终点的所有合法路径数

2. 动态规划建模

状态定义

dp[i][j]表示从起点(0,0)到达坐标(i,j)的合法路径总数

状态转移

$\begin{cases} 0 & \text{当前位置被马控制} \\ 1 & \text{i=0且j=0（起点）} \\ dp[i-1][j] + dp[i][j-1] & \text{其他情况} \end{cases}$

初始化条件

dp[0][0] = 1（起点自身算1条路径）
被马控制的位置及其后续位置保持0值

3. 关键优化

坐标系偏移

将原始坐标系整体右移2格，下移2格（代码中b1 += 2; b2 += 2），目的是：

避免处理负数坐标
统一处理棋盘边界（通过循环条件i <= b1和j <= b2自动限制范围）

马控制范围判断

通过预定义的8个方向向量：

int dx[8] = {-2,-2,-1,+1,+2,+2,+1,-1};
int dy[8] = {-1,+1,+2,+2,+1,-1,-2,-2};

检查目标位置是否被马控制：

bool pd(int a, int b) {// 检查马本体位置if (m1 == a && m2 == b) return false;// 检查8个控制位for (int i = 0; i < 8; ++i) {if (m1 + dx[i] == a && m2 + dy[i] == b) return false;}return true;
}

代码解析

1. 输入处理

cin >> b1 >> b2 >> m1 >> m2;
b1 += 2;  // 扩展后的棋盘行数
b2 += 2;  // 扩展后的棋盘列数
m1 += 2;  // 马坐标同步偏移
m2 += 2;

2. 动态规划核心

for (int i = 2; i <= b1; ++i) {        // 遍历所有行for (int j = 2; j <= b2; ++j) {    // 遍历所有列if (!pd(i, j)) {               // 被马控制的位置dp[i][j] = 0;continue;}if (i == 2 && j == 2) {        // 起点初始化dp[i][j] = 1;continue;}dp[i][j] = dp[i-1][j] + dp[i][j-1];  // 状态转移}
}

3. 输出结果

最终结果存储在dp[b1][b2]中，直接输出即可。

复杂度分析

时间复杂度：O(nm)，仅需遍历棋盘一次
空间复杂度：O(nm)，使用二维数组存储状态

常见错误及注意事项

坐标偏移：忘记对马的位置进行同步偏移会导致控制范围判断错误
边界条件：当马位于起点或终点时，路径数应为0
数据类型：路径数可能超过int范围，需使用long long类型
初始化顺序：必须按行优先顺序填充dp数组，保证状态转移的正确性

扩展思考

记忆化搜索：可用DFS+记忆化实现，但时间复杂度较高（O(2^(n+m))）
矩阵快速幂：对于无阻挡的纯路径计数问题，可用组合数学优化到O(log(n+m))
三维DP：当需要记录更多状态时（如不同移动方式），可扩展DP维度

总结

本题通过动态规划完美解决了路径计数问题，关键点在于：

合理建模状态转移方程
正确处理棋盘边界和阻挡条件
通过坐标偏移简化边界判断

该方法的时间复杂度稳定在O(nm)，能够高效处理题目给定的数据范围（n,m ≤ 20），是典型的动态规划应用案例。

每日c/c++题备战蓝桥杯(P1002 [NOIP 2002 普及组] 过河卒)

洛谷P1002 [NOIP 2002 普及组] 过河卒题解题目描述过河卒是一道经典的动态规划题目。题目大意是：一个卒子从棋盘左上角(0,0)出发，要走到右下角(n,m)，棋盘上有一个马在(x,y)位置，卒子不能经过马所在位置及其周围8个位置。求卒…...

编程日记 2025/7/27 17:39:50

kubectl系列(十二)：查询pod的resource 配置

在 Kubernetes 中，可以通过 kubectl 命令快速查询 Pod 的资源请求（requests）和限制（limits）配置。以下是多种方法实现这一目标： 1. 查看 Pod 的资源请求和限制（基础版） 使用 kubec…...

编程日记 2025/7/27 21:22:00

前端面试2

1. 面试准备 1. 建立自己的知识体系思维导图ProcessOn框架Vue elementUI自查 https://zh.javascript.info/ 借鉴 https://juejin.cn/post/6844904103504527374http://conardli.top/blog/article/https://github.com/mqyqingfeng/Bloghttp://47.98.159.95/my_blog/#html 2.技能…...

编程日记 2025/7/27 21:35:15

使用 Java 反射动态加载和操作类

Java 的反射机制（Reflection）是 Java 语言的一大特色，它允许程序在运行时检查、加载和操作类、方法、字段等元信息。通过 java.lang.Class 和 java.lang.reflect 包，开发者可以动态加载类、创建实例、调用方法，甚至在运行时构造新类。反射是 Java 灵活性的核心，广泛应用于…...

编程日记 2025/7/27 21:46:31

基于Dockers的Bitwarden的私有本地部署

基于Dockers的Bitwarden的私有本地部署文章目录基于Dockers的Bitwarden的私有本地部署本文首发地址 https://h89.cn/archives/355.html bitwarden 默认连接的是国外服务器 https://bitwarden.com/ ，连接不是很稳定，也没有安全感，所以我选择…...

编程日记 2025/7/27 21:18:08

spark-Schema 定义字段强类型和弱类型

在数据处理和存储中，Schema（模式）定义了数据的结构和字段属性，其中字段的强类型和弱类型是重要的概念，直接影响数据的验证、存储和处理方式。以下是详细解释： 1. 强类型（Strongly Typed&#x…...

编程日记 2025/7/27 21:40:36

【第35节数据库设计】

本章目录: 一、节概述二、知识详解1. 数据库设计的基本步骤2. 用户需求分析3. 概念结构设计（E-R建模）4. 逻辑结构设计5. 物理结构设计6. 数据库实施7. 数据库运行维护8. 商业智能（BI）与数据仓库数据仓库的特点： 9. OLT…...

编程日记 2025/7/27 20:31:48

C++基本知识 —— 缺省参数·函数重载·引用

C基本知识 —— 缺省参数函数重载引用 1. 缺省参数2. 函数重载3. 引用3.1 引用的基础知识3.2 引用的作用3.3 const 引用3.4 指针与引用的关系 1. 缺省参数什么是缺省参数？缺省参数是声明或定义函数时为函数的参数指定一个缺省值。在调用该函数的时候，如…...

编程日记 2025/7/27 21:29:12

大数据基础——Ubuntu 安装

文章目录 Ubuntu 安装一、配置电脑二、安装系统 Ubuntu 安装一、配置电脑 1、进入VMware 2、选择配置类型 3、选择硬件兼容性版本 4、当前虚拟机的操作系统选择“稍后安装操作系统”（修改） 5、选择虚拟机将来需要安装的系统选中“Linux”和选择…...

编程日记 2025/7/27 21:29:11

英伟达微调qwen2.5-32B模型，开源推理模型：OpenCodeReasoning-Nemotron-32B

一、模型概述 OpenCodeReasoning-Nemotron-32B 是一个大型语言模型，基于 Qwen2.5-32B-Instruct 开发，专为代码生成推理任务进行了后续训练，支持 32,768 个标记的上下文长度，适用于商业和非商业用途。二、性能表现在 LiveCode…...

编程日记 2025/7/27 19:46:48

苍穹外卖-创建阿里云oss工具包

添加配置信息： sky:alioss:endpoint: ***access-key-id: ***access-key-secret: ***bucket-name: *** 把配置的内容转换成对象： Component ConfigurationProperties(prefix "sky.alioss") Data public class AliOssProperties {private St…...

编程日记 2025/7/27 21:37:15

代码随想录训练营第二十一天 |589.N叉数的前序遍历 590.N叉树的后序遍历

589.N叉数的前序遍历： 状态：已做出思路： N叉树的前序遍历和二叉树很像，我这里使用栈来实现。首先把根结点入栈，然后删除栈顶节点后把栈顶节点的所有子树都插入到栈，这里需要注意的是插入的方式是从最后一…...

编程日记 2025/7/27 21:23:52

鸿蒙跨平台开发教程之Uniapp布局基础

前两天的文章内容对uniapp开发鸿蒙应用做了一些详细的介绍，包括配置开发环境和项目结构目录解读，今天我们正式开始写代码。入门新的开发语言往往从Hello World开始，Uniapp的初始化项目中已经写好了一个简单的demo，这里就不再赘述…...

编程日记 2025/7/27 21:36:03

面试中常问的设计模式及其简洁定义

🎯 一、面试中常问的设计模式及其简洁定义模式名常被问到解释（简洁）单例模式✅ 高频保证一个类只有一个实例，并提供全局访问点。工厂模式✅ 高频创建对象的接口由子类决定，屏蔽了对象创建逻辑。抽象工厂模式✅提供多…...

编程日记 2025/7/27 21:39:59

关于 js：6. 网络与加密模块

一、AJAX AJAX（Asynchronous JavaScript And XML） 异步 JavaScript 与 XML（现在多为 JSON） 它允许网页在不重新加载整个页面的情况下，从服务器请求数据并更新页面内容。主要用途： 提交表单时无需刷新页…...

编程日记 2025/7/27 21:40:36

量化交易系统开发经验分享--回测框架调研

一、前言这段时间在集中做一个量化交易系统的开发任务，目前系统的MVP已经完成开发，后续会整理一些经验与成果和大家交流。刚好有一个前期做策略回测这块的调研，下面把调研的成果做一个整理总结先给大家分享一下，请批评指正。在介…...

编程日记 2025/7/27 21:39:58

[学习]RTKLib详解：convkml.c、convrnx.c与geoid.c

本文是 RTKLlib详解系列文章的一篇，目前该系列文章还在持续总结写作中，以发表的如下，有兴趣的可以翻阅。 [学习] RTKlib详解：功能、工具与源码结构解析 [学习]RTKLib详解：pntpos.c与postpos.c [学习]RTKLib详解&…...

编程日记 2025/7/27 21:24:28

【ajax基础】

提示：文章为学习过程中的记录实践笔记。有问题欢迎指正。文章目录前言一、实现步骤二、完整示例三、封装总结前言 AJAX 不是编程语言，是一种从网页访问web服务器的技术。可以实现不刷新页面更新网页在页面加载后从服务器请求/获取数据在后台向服…...

编程日记 2025/7/27 21:28:36

Nodejs核心机制

文章目录前言前言结合 Node.js 的核心机制进行说明： 解释事件循环的各个阶段。答案 Node.js 事件循环分为 6 个阶段，按顺序执行： Timers：执行 setTimeout 和 setInterval 的回调。 Pending I/O Callbacks：处理系…...

编程日记 2025/7/27 21:33:44

Kubernetes 集群部署应用

部署 Nginx 应用命令行的方式 1. 创建 deployment 控制器的 pod # --imagenginx：这个会从 docker.io 中拉取，这个网站拉不下来 # kubectl create deployment mynginx --imagenginx# 使用国内镜像源拉取 kubectl create deployment mynginx --imaged…...

编程日记 2025/7/27 21:33:42

【Linux篇】高并发编程终极指南：线程池优化、单例模式陷阱与死锁避坑实战

深入理解线程池设计与应用：高效并发编程的秘密一. 线程池1.1 什么是线程池1.2 线程池的优点1.3 线程池的应用场景二. 线程池设计三. 单例模式3.1 什么是单例模式3.2 单例模式特点3.3 实现单例模式方法3.3.1 饿汉实现⽅式3.3.2 懒汉实现⽅式四. 线程安全和重入问题…...

编程日记 2025/7/27 21:33:40

学习和测试WebApi项目限制客户端ip访问接口（基于中间件）

WebApi项目需要限制仅允许有限的客户端访问接口，百度相关内容，网上很多介绍WebApi接口IP限流的文章，稍微调整就能用于限制IP访问，微软官网中也有文章介绍客户端 IP 安全列表（参考文献1），可以通过…...

编程日记 2025/7/27 21:33:38

闲鱼智能客服机器人-实现闲鱼平台7×24小时自动化值守

专为闲鱼平台打造的AI值守解决方案，实现闲鱼平台724小时自动化值守，支持多专家协同决策、智能议价和上下文感知对话。 🌟 核心特性智能对话引擎功能模块技术实现关键特性上下文感知会话历史存储轻量级对话记忆管理，完整对话历…...

编程日记 2025/7/27 21:33:36

Apache Ranger 2.2.0 编译

安装包下载： https://ranger.apache.org/download.html 编译环境： Linux centos7jdk 1.8maven 3.9.6gitpython 3 git 安装 yum -y install gitpython3安装 yum install epel-release -y yum install python3 python3-devel -y批量安装开发工具套件 …...

编程日记 2025/7/27 21:33:34

实战演练：用 AWS Lambda 和 API Gateway 构建你的第一个 Serverless API

实战演练：用 AWS Lambda 和 API Gateway 构建你的第一个 Serverless API 理论千遍，不如动手一遍！在前面几篇文章中，我们了解了 Serverless 的概念、FaaS 的核心原理以及 BaaS 的重要作用。现在，是时候把这些知识运用起来，亲手构建一个简单但完整的 Serverless 应用了。 …...

编程日记 2025/7/27 21:33:32

鱼眼相机生成-BEV鸟瞰图-入门教程

目录原理介绍 1. ‌IPM与BEV转换的核心原理‌ 2. ‌尺度信息的来源‌ 3. ‌尺度信息的准确性限制‌ 4. ‌实际应用中的处理方法‌ 代码实现： 360 BEV环视拼接算法一、核心算法流程‌ 三、实际应用挑战与优化‌ 四、开源实现参考原理介绍 1. ‌IPM与BEV转换的核心…...

编程日记 2025/7/27 1:22:44

设计模式简述（十八）享元模式

享元模式描述基本组件使用描述当内存中存在大量类似的对象时，可以考虑使用享元模式减少整体内存占用。可以将相同的部分和不同的部分进行拆分，以达到多个对象共享相同部分内存的目的。基本组件通常享元对象通过共享的属性映射一个享元对象。公…...

编程日记 2025/7/27 21:33:28

Google语法整理

以下是从整理出的 Google 语法： site：指定域名，如 “apache site:bbs.xuegod.cn”，可查询网站的收录情况。 inurl：限定在 url 中搜索，如 “inurl:qq.txt”，可搜索 url 中包含特定内容的页面&a…...

编程日记 2025/7/27 17:54:41

【每日一题 | 2025年5.5 ~ 5.11】搜索相关题

个人主页：Guiat 归属专栏：每日一题文章目录 1. 【5.5】P3717 [AHOI2017初中组] cover2. 【5.6】P1897 电梯里的尴尬3. 【5.7】P2689 东南西北4. 【5.8】P1145 约瑟夫5. 【5.9】P1088 [NOIP 2004 普及组] 火星人6. 【5.10】P1164 小A点菜7. 【5.11】P101…...

编程日记 2025/7/24 13:40:41

【MySQL】页结构详解：页的大小、分类、头尾信息、数据行、查询、记录及数据页的完整结构

📢博客主页：https://blog.csdn.net/2301_779549673 📢博客仓库：https://gitee.com/JohnKingW/linux_test/tree/master/lesson 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！ &…...

编程日记 2025/7/25 4:24:27

C++ stl中的priority_queue的相关函数用法

文章目录 priority_queuepriority_queue定义方式priority_queue相关函数 priority_queue priority_queue 称为优先级队列，默认使用vector作为底层存储数据的容器，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用…...

编程日记 2025/7/26 8:55:39

软件架构师知识点总结

一、综合知识软件架构师综合知识总结-CSDN博客二、案例软件架构师案例知识点总结-CSDN博客三、论文 1、题目类型：八大架构；系统开发（开发方法/模型、需求分析、测试等）；系统可靠性、安全性、容错技术等&#…...

编程日记 2025/7/23 21:23:05

MySQL数据库常见面试题之三大范式

写在前面此文章大部分不会引用最原始的概念，采用说人话的方式。面试题：三大范式是什么？目的是什么？必须遵循吗？ 假设有一张表（学号，姓名，课程，老师） 是…...

编程日记 2025/7/24 19:14:37

Scrapy 核心组件解析：Request Response 的深度应用与实战

Scrapy 是 Python 生态中最强大的爬虫框架之一，其核心组件 Request 和 Response 承担着数据抓取与处理的关键任务。本文深入解析 Scrapy 2.13.0 中 Request 和 Response 的高级用法，涵盖参数配置、回调函数、错误处理、子类扩展等，并结合综合…...

编程日记 2025/7/25 11:38:39

mybatis执行sql过程

一、配置加载阶段 1. 读取全局配置（mybatis-config.xml） 入口类：SqlSessionFactoryBuilder.build()关键组件： XMLConfigBuilder：解析全局配置文件。Configuration：存储所有配…...

编程日记 2025/7/24 16:43:05

OceanBase 4.3版本向量数据库部署

OceanBase 4.3版本向量数据库部署安装包准备最低资源配置重要的准备事项服务器配置操作系统内核参数BIOS设置磁盘挂载网卡设置部署OAT工具初始化OBServer服务器使用oatcli部署OB集群安装OceanBase软件初始化OceanBase集群启用向量检索功能 OceanBase最新的V4.3版本开始支持向…...

编程日记 2025/7/26 1:38:33

LeetCode 941. 有效的山脉数组 java题解

https://leetcode.cn/problems/valid-mountain-array/description/ 双指针 class Solution {public boolean validMountainArray(int[] arr) {int lenarr.length;if(len<3) return false;int left0,rightlen-1;while(left1<len&&arr[left]<arr[left1]){left…...

编程日记 2025/7/25 6:53:47

基于Java和高德开放平台的WebAPI集成实践-以搜索POI2.0为例

目录前言一、高德搜索API简介 1、高德开放平台 2、搜索功能介绍 3、部分API介绍二、Uniapi集成高德API 1、API集成流程 2、访问接口的定义 3、业务调用集成三、常见问题与优化四、总结前言在当今数字化时代，地理信息系统（GIS&#xff…...

编程日记 2025/7/24 23:52:33

Docker拉取ubuntu22.04镜像使用ROS2 humble及仿真工具可视化进行导航

创建Ubuntu22.04 容器 docker pull ubuntu:22.04 #下载22.04镜像 docker images #查看已下载镜像 #根据镜像创建容器 sudo docker run -it -v /home/lab118/BD_ICL/tools_BD/cailib_data:/calib_data -v /tmp/.X11-unix:/tmp/.X11-unix -e DISPLAY:0 --nethost -e GDK_SCAL…...

编程日记 2025/7/24 16:41:52

PXE安装Ubuntu系统

文章目录 1. 服务器挂载Ubuntu镜像2. 修改dhcp配置文件3. 修改tftp配置文件4.复制网络驱动文件和其他配置文件5. http目录下配置文件6. 踩坑记录6.1 Failed to load ldlinux.c326.2 no space left on device6.3 为啥用pxe安装系统时，客户端需要较大的内存&#xff1…...

编程日记 2025/7/25 15:36:51

外网访问内网海康威视监控视频的方案：WebRTC + Coturn 搭建

外网访问内网海康威视监控视频的方案：WebRTC Coturn 需求背景在仓库中有海康威视的监控摄像头，内网中是可以直接访问到监控摄像的画面，由于项目的需求，需要在外网中也能看到监控画面。实现这个功能的意义在于远程操控设备的…...

编程日记 2025/7/27 8:56:31

缓存局部性保留

在操作系统中，线程切换相比进程切换更轻量级的关键原因之一是缓存（Cache）的有效性，尤其是对 CPU 缓存（如 L1/L2/L3）和 TLB（Translation Lookaside Buffer）的影响。以下从缓存角度详…...

编程日记 2025/7/23 11:00:46

MyBatis源码解读5（3.1、缓存简介）

3.1、简介我们需要记住一句话，程序与数据库之间的交互是性能瓶颈的关键，所以我们在做优化的时候，数据库的优化要做，但是优先级是最低的，比它优先级高的是方面是程序与数据库之间的交互，先从宏观上解决…...

编程日记 2025/7/20 23:32:02

【MySQL】行结构详解：InnoDb支持格式、如何存储、头信息区域、Null列表、变长字段以及与其他格式的对比

编程日记 2025/7/24 1:19:35

Docker 部署Nexus仓库搭建Maven私服仓库公司内部仓库

介绍 Nexus 是广泛使用的仓库管理工具，常用于管理 Java 构件（如 JAR、WAR、EAR 文件）。它可以作为一个本地的 Maven 仓库，用来存储和管理项目的依赖包和构建产物。支持多种仓库类型，能够帮助开发团队更高效地管理构件…...

编程日记 2025/7/26 23:43:11

PostgreSQL 的 pg_column_size 函数

PostgreSQL 的 pg_column_size 函数 pg_column_size 是 PostgreSQL 提供的一个系统函数，用于返回特定列或值在数据库内部存储时所占用的字节数。这个函数对于数据库优化、存储空间分析和性能调优非常有用。函数语法 pg_column_size(anyelement)参数说明 anyele…...

编程日记 2025/7/24 1:09:16

【前端】【HTML】【总复习】一万六千字详解HTML 知识体系

🌐 HTML 知识体系一、HTML 基础入门 1. HTML 简介与作用 HTML（HyperText Markup Language，超文本标记语言）是构建网页的基础语言。它的核心作用是：定义网页内容的结构（标题、段落、图片、表格等）提供语义化标签，帮助搜索引擎与辅助设备理解页面内容配合 CSS 实现…...

编程日记 2025/7/25 7:12:48

支持向量机与逻辑回归的区别及 SVM 在图像分类中的应用

支持向量机与逻辑回归的区别及 SVM 在图像分类中的应用在机器学习的多元算法领域中，支持向量机（SVM）和逻辑回归（LR）作为两种经典的监督学习算法，被广泛应用于各类分类任务。尽管它们有着相似的目标&#…...

编程日记 2025/7/23 14:27:23

MySQL基础面试题集锦

MySQL基础面试题集锦一、SQL基础语法 1. 数据库和表操作 -- 创建数据库 CREATE DATABASE test_db CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci;-- 创建表 CREATE TABLE users (id INT AUTO_INCREMENT PRIMARY KEY,username VARCHAR(50) NOT NULL UNIQUE,email VARCH…...

编程日记 2025/7/25 23:14:23

【网络分析工具】网络工具wireshark、TCPdump、iperf使用详解

这里写目录标题 1. wireshark1.1. 过滤包1.2. 常见分析 2. tcpdump3. iperf 1. wireshark **ip.dst eq 10.0.0.21** 是用于网络流量分析工具（例如 Wireshark 或 tcpdump）的过滤器表达式。它的作用是筛选出所有目标IP地址为 10.0.0.21 的数据包 IP.add…...

编程日记 2025/7/19 22:28:51

洛谷P1002 [NOIP 2002 普及组] 过河卒 题解