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

【算法1-4】递推与递归-P1002 [NOIP2002 普及组] 过河卒

## 题目描述

棋盘上 A 点有一个过河卒,需要走到目标 B 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示,A 点 (0, 0)、B$点 (n, m),同样马的位置坐标是需要给出的。

现在要求你计算出卒从 A 点能够到达 B 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。

## 输入格式

一行四个正整数,分别表示 B 坐标和马的坐标。

## 输出格式

一个整数,表示所有的路径条数。

## 样例 #1

### 样例输入 #1
6 6 3 3

### 样例输出 #1
6

## 提示

对于 100 % 的数据,1≤n,m≤20,0≤ 马的坐标 ≤20。

分析:

首先要先考虑递推式,并且考虑终止条件

我们对于要到达的b(xb,yb)点,设置一个f(x,y),表示从0,0走到f点的可能数

对于任意的一个点,如果想到达本点,只能从左方和上方移动过来

本点坐标如果为x,y则左边点坐标为(x-1,y)上边点坐标为(x,y-1),如果说从左边到本点的可能性为a,从上边到本点的可能性为b,则到达本点总可能性为a+b

因此我们可以得出递推式:f(x,y)=f(x-1,y)+f(x,y-1)

终止条件:

首先第一个点(0,0)到达这个点的可能次数只有1,而(0,y)(x,0)这两条边界的点到达可能同样也只有一种,最后是马以及马脚所在的点,到达的可能性一定为0。

分析完毕,思考解题思路,首先对数据进行输入,用二维数据来模拟棋盘,如果不能走就赋值为1,反之为0。再设置一个二维数组来对f函数即可能到达的可能性进行记录,像是边界直接给赋值1,之后利用递推式依次递推到B点就可以了

一、输入

这边有一个问题,就是如果我的马在1行或者存在于1列,必然会导致,马脚超出数组范围,我们可以建立保护层来方式超出,就是将每个点都+2使得整体往右下偏移,这样最远的马脚也只能到达0行0列,不会超出。

开始定义 马点,B点,以及棋盘和对应点的可能

long long xb,yb,xh,yh;
long long pand[30][30]={0},f[30][30]={0};

依次输入之后做偏移

    cin>>xb>>yb>>xh>>yh;xb += 2; yb += 2;xh += 2; yh += 2;

二、对边界进行赋值

边界到达的可能只有1,所以可以直接赋值

for(int i=2;i<30;i++){f[2][i] = 1;f[i][2] = 1;
}

 三、马对应的特殊点进行赋值

在地图上的我们对不能到达也就是可能性为0的点进行标注

    pand[xh][yh] = 1;pand[xh-2][yh-1] = 1;pand[xh-1][yh-2] = 1;pand[xh+2][yh+1] = 1;pand[xh+1][yh+2] = 1;pand[xh+2][yh-1] = 1;pand[xh+1][yh-2] = 1;pand[xh-2][yh+1] = 1;pand[xh-1][yh+2] = 1;

四、递推的计算f(x,y)

 在这里通过递推式会遇到问题是0,0点也是现如今的2,2点,因为前面的两点的f函数都为0所以将f1,2或者f2,1赋值为1即可

之后通过递推公式,依次判断,如果遇到马或者马脚,就将可能性为0,代表此路不通直接continue

    f[1][2] = 1;for(int i = 2;i<=xb;i++){for(int j = 2;j<=yb;j++){if(pand[i][j]==1){f[i][j] = 0;continue;}f[i][j]= f[i-1][j]+f[i][j-1];}}

五、输出

 直接将f函数可能性输出即可;

完整代码:

#include <bits/stdc++.h>
using namespace std;
long long xb,yb,xh,yh;
long long pand[30][30]={0},f[30][30]={0};
int main(){cin>>xb>>yb>>xh>>yh;xb += 2; yb += 2;xh += 2; yh += 2;for(int i=2;i<30;i++){f[2][i] = 1;f[i][2] = 1;}pand[xh][yh] = 1;pand[xh-2][yh-1] = 1;pand[xh-1][yh-2] = 1;pand[xh+2][yh+1] = 1;pand[xh+1][yh+2] = 1;pand[xh+2][yh-1] = 1;pand[xh+1][yh-2] = 1;pand[xh-2][yh+1] = 1;pand[xh-1][yh+2] = 1;f[1][2] = 1;for(int i = 2;i<=xb;i++){for(int j = 2;j<=yb;j++){if(pand[i][j]==1){f[i][j] = 0;continue;}f[i][j]= f[i-1][j]+f[i][j-1];}}cout<<f[xb][yb];return 0;
}

相关文章:

【算法1-4】递推与递归-P1002 [NOIP2002 普及组] 过河卒

## 题目描述 棋盘上 A 点有一个过河卒&#xff0c;需要走到目标 B 点。卒行走的规则&#xff1a;可以向下、或者向右。同时在棋盘上 C 点有一个对方的马&#xff0c;该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示&#…...

浅谈压力测试的作用是什么

随着现代应用程序变得越来越复杂&#xff0c;用户的期望也在不断提高&#xff0c;对性能和可靠性的要求变得更加苛刻。在应用程序开发和维护的过程中&#xff0c;压力测试是一项至关重要的活动&#xff0c;它可以帮助发现潜在的问题、评估系统的性能极限&#xff0c;以及确保在…...

互联网Java工程师面试题·Java 总结篇·第一弹

目录 1、面向对象的特征有哪些方面&#xff1f; 2、访问修饰符 public,private,protected,以及不写&#xff08;默认&#xff09;时的区别&#xff1f; 3、String 是最基本的数据类型吗&#xff1f; 4、float f3.4;是否正确&#xff1f; 5、short s1 1; s1 s1 1;有错吗…...

Anylogic 读取和写入Excel文件

1、选择面板-连接-Excel文件&#xff0c;拖入到视图中 然后在excel文件的属性中进行绑定外部excel文件。 绑定完之后&#xff0c;在你需要读取的地方进行写代码&#xff0c; //定义开始读取的行数 //这里设为2&#xff0c;是因为第一行是数据名称 int row12; //读取excel文件信…...

茶百道全链路可观测实战

作者&#xff1a;山猎 茶百道是四川成都的本土茶饮连锁品牌&#xff0c;创立于 2008 年 。经过 15 年的发展&#xff0c;茶百道已成为餐饮标杆品牌&#xff0c;全国门店超 7000 家&#xff0c;遍布全国 31 个省市&#xff0c;实现中国大陆所有省份及各线级城市的全覆盖。2021 …...

Java-JDBC

JDBC JDBC英文名为&#xff1a;Java Data Base Connectivity(Java数据库连接)&#xff0c;官方解释它是Java编程语言和广泛的数据库之间独立于数据库的连接标准的Java API 根本上说JDBC是一种规范&#xff0c;它提供的接口&#xff0c;一套完整的&#xff0c;允许便捷式访问底…...

【ROS】Nav2源码之nav2_planner详解

【ROS】郭老二博文之:ROS目录 1、简述 nav2_planner是路径规划器,把起始位置、姿势的信息输入nav2_planner模块,将会生成可行路径。 nav2_planner路径规划器和nav2_controller控制器相似,也使用插件的形式加载不同的路径规划器。 常用的路径规划器插件有: 1)NavFn Plan…...

mysql报SQLSTATE[22007]的错误的一个原因

最近在修改一个程序&#xff0c;打算将$video这个参数保存到数据库。修改的过程中出现错误。导致该程序不能发布新文章。在程序的一个db.php程序文件里使用var_dump($input, $stmt) ; 语句看到了错误信息&#xff0c;并找到了错误原因。信息里包含的错误代码是&#xff1a; SQ…...

Python —— UI自动化之 三大等待与三大切换

1、三大等待 1、硬性等待 1、概述 硬性等待也可以称之为强制等待&#xff0c;写法如下&#xff1a; time.sleep() 优点&#xff1a;使用简单 缺点&#xff1a;等待时间把握不准&#xff0c;容易造成时间浪费或者等待时间不足 2、实战 from time import sleep from sele…...

初识容器Docker

目前使用 Docker 基本上有两个选择&#xff1a;Docker Desktop和Docker Engine。Docker Desktop 是专门针对个人使用而设计的&#xff0c;支持 Mac 和 Windows 快速安装&#xff0c;具有直观的图形界面&#xff0c;还集成了许多周边工具&#xff0c;方便易用。 不是太推荐使用D…...

pikachu靶场搭建及通关

一、靶场搭建 下载工具&#xff1a;phpstudy Pikachu靶机下载地址&#xff1a; https://github.com/zhuifengshaonianhanlu/pikachu 下载后解压缩并放入如下文件夹&#xff08;网站根目录&#xff09; 建议修改文件名称为 pikachu 修改配置文件&#xff08;mysql 用户名&…...

选择排序(学习笔记)

选择排序 选择排序的基本思想是冒泡排序&#xff0c;记录当前位置i和最小值k的位置&#xff0c;使用一个变量j往后寻找。 每一轮找到最小值后与第一个元素进行交换&#xff0c;以此类推。 不使用辅助变量交换两个元素的值方法 package com.company.sort;import java.util.Ra…...

PCL 生成球形点云

目录 一、算法原理二、代码实现三、结果展示四、参考链接一、算法原理 生成球体点云的方法有很多种,Marsaglia于1972年提出了一个简单易行的实现方法,它从(-1,1)上的独立均匀分布中选取 x 1 x_1 x...

Flutter 剪裁(Clip)

&#x1f525; ClipOval &#x1f525; 子组件为正方形时剪裁成内贴圆形&#xff1b;为矩形时&#xff0c;剪裁成内贴椭圆 裁剪纯色背景 ClipOval(child: Container(width: 300.w,height: 300.w,decoration: const BoxDecoration(color: Colors.red),),), 裁剪背景图片 裁剪前…...

嵌入式C语言自我修养《GNU C编译器扩展语法》学习笔记

目录 一、C语言标准和编译器 二、指定初始化 三、宏构造“利器”&#xff1a;语句表达式 四、typeof与container_of宏 五、零长度数组 六、属性声明&#xff1a;section 七、属性声明&#xff1a;aligned 一、C语言标准和编译器 C语言标准的发展过程&#xff1a; ●…...

密码学二: md5 网站服务器与用户通信过程 ca原理 签名原理 Flame 病毒原理

md5被破解? MD5&#xff08;Message Digest Algorithm 5&#xff09;是一个较早的哈希函数&#xff0c;但由于其弱点和漏洞&#xff0c;它已经被认为不再适合用于安全性要求较高的应用。MD5的一些安全性问题包括&#xff1a; 碰撞攻击&#xff1a; MD5已经被证明容易受到碰撞攻…...

Zend Framework 3.1.3 gadget chain

前言 在推特上的PT SWARM账号发布了一条消息。 一个名为Zend Framework的php框架出现了新的gadget chain&#xff0c;可导致RCE。笔者尝试复现&#xff0c;但失败了。所幸&#xff0c;我基于此链&#xff0c;发现在这个框架的最新版本中的另一条链。 复现过程 这里使用vscod…...

互联网Java工程师面试题·Java 并发编程篇·第四弹

目录 39、volatile 有什么用&#xff1f;能否用一句话说明下 volatile 的应用场景&#xff1f; 40、为什么代码会重排序&#xff1f; 41、在 java 中 wait 和 sleep 方法的不同&#xff1f; 42、用 Java 实现阻塞队列 43、一个线程运行时发生异常会怎样&#xff1f; 44、…...

3、Linux下安装

以下操作仅限于rh系列:支持rpm/yum安装方式&#xff0c;不支持deb/apt安装方式。 以下操作仅限于rh系列&#xff1a;支持rpm/yum安装方式&#xff0c;不支持 deb/apt安装方式。 1、在线下载安装包&#xff1a; wget https://downloads.mysql.com/archives/get/p/23/file/ m…...

Zookeeper【Curator客户端Java版】从0到1——万字学习笔记

目录 初识Zookeeper Zookeeper作用 维护配置信息 分布式锁服务 集群管理 生产分布式唯一ID Zookeeper的设计目标 Zookeeper 工作机制 数据模型 ZooKeeper 命令操作 服务端常用命令 客户端常用命令 ZooKeeper JavaAPI操作 Curator 介绍 Curator API 常用操作 导入依赖 建立连接 …...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

【实施指南】Android客户端HTTPS双向认证实施指南

&#x1f510; 一、所需准备材料 证书文件&#xff08;6类核心文件&#xff09; 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...