趣味算法------过河卒

 

目录

​编辑

题目描述

解题思路

具体代码

总结

问题描述:

解决方案:

代码实现:

关键点:


题目描述


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

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


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

输入格式
一行四个正整数,分别表示 B 点坐标和马的坐标。

输出格式
一个整数,表示所有的路径条数。

输入输出样例
输入 1
6 6 3 3
输出 1
6
输入 6 6 表示 B 点的坐标,3 3 表示马的坐标,输出 6 表示除去马的坐标以及所有跳跃一步可达的点,从 A 点出发到 B 点的所有的路径条数。

解题思路

        在解决这个问题之前我要先引入一个例子,假设小明站在二维坐标图的原点位置,并且一次只能走上右一格距离,并且已经走过的地方不能再走,而且只能走最短距离,那么他到(1,0),(0,1)方案肯定是1,那么(1,1)方案数就为2,由(1,1)再往外扩展的一个方案数就为3,是典型的动态规划问题。

        

代码的思路是使用动态规划来解决“马拦过河卒”问题。动态规划数组arr的大小为maxlen x maxlen,用于存储从起点(0,0)到棋盘上每个点的路径数量。

  1. 函数check_place用于检查给定的点(r, l)是否在马的控制范围内。马的移动方向由数组dir定义,包含了马的八个可能的移动方向。

  2. 初始化时,如果起点(0,0)不在马的控制范围内,则将arr[0][0]设置为1。

  3. 接着,对于起点行和列的其他点,如果不在马的控制范围内,也将相应的arr元素设置为1,这是因为卒可以直接从起点到达这些点。

  4. 对于棋盘上的其他点,卒可以通过向下或向右移动到达。如果当前点(i, j)不在马的控制范围内,则其路径数量为上一行对应点和左一列对应点路径数量之和,即arr[i][j] = arr[i - 1][j] + arr[i][j - 1]

  5. 最后,输出数组中目标点(M, N)的值,即为卒从起点到目标点的路径数量。

这种方法的时间复杂度为O(MN),空间复杂度为O(MN),其中M和N分别是棋盘的行数和列数。通过这种方式,代码能够计算出在马的控制下,卒从起点到目标点的所有可能路径的数量。

具体代码

#include<stdio.h>
#include<stdlib.h>
#define maxlen 100
int check_place(int r, int l, int h_r, int h_l)
{int dir[8][2] = { {2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2} };for (int i = 0; i < 8; i++)if ((dir[i][1] + h_l == l && dir[i][0] + h_r == r)||(r == h_r &&h_l == l))return 1;return 0;
}
int main(void)
{int arr[maxlen][maxlen] = { {1} };int M, N, m, n;scanf("%d%d%d%d", &M, &N, &m, &n);for (int i = 1; i <= N; i++){if (!check_place(0, i, m,n))arr[0][i] = 1;elsebreak;}for (int i = 1; i <= M; i++){if (!check_place(i, 0, m,n))arr[i][0] = 1;elsebreak;}for(int i = 1;i<=M;i++)for (int j = 1; j <= N; j++){if (!check_place(i, j, m, n))arr[i][j] = arr[i - 1][j] + arr[i][j - 1];}printf("%d", arr[M][N]);return 0;}

总结

问题描述:


在棋盘上,有一个过河卒从点A(0,0)出发,目标是到达点B(n,m)。过河卒可以向下或向右移动。棋盘上存在一个对方的马,位于点C。马及其控制的八个方向上的点被定义为“马的控制点”。任务是计算出卒从A点到达B点的路径数量,且这些路径不能经过马的控制点。

解决方案:

  1. 定义控制点: 马的控制点包括马所在位置及其八个方向上可以到达的点。通过一个辅助函数check_place判断任意点是否为控制点。
  2. 动态规划:
    • 初始化一个二维数组arr,其中arr[i][j]表示从A点到达(i,j)的路径数量。
    • 初始条件:arr[0][0] = 1,表示起点到自身的路径数量为1。
    • 对于第一行和第一列,如果不在马的控制点范围内,则arr[i][0]arr[0][j]的值为1,表示可以直接到达。
    • 通过动态规划递推公式arr[i][j] = arr[i-1][j] + arr[i][j-1]更新其他点的路径数量,前提是该点不在马的控制点范围内。
  3. 输出结果: 最终,arr[n][m]即为从A点到B点的路径数量。

代码实现:


使用C语言实现上述逻辑,通过check_place函数判断控制点,使用动态规划计算路径数量。

关键点:

  • 动态规划的递推关系和边界条件设置。
  • 识别并排除马的控制点。

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

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

相关文章

自动化通过cmd命令行并以特定账户连接到远程机器

1 建一个taskschedule运行cmd命令 2 cmd命令示例&#xff1a; 机器名加域名 mstsc /v:"<MachineName>.xxx.xxx.com"或者是机器IP地址 mstsc /v:"10.148.66.178"3 设置用特定账户登陆 用户名可以写 <要连接的机器名><用户名> 勾选“记住…

川崎机器人维修请开启马达电源报警故障

‌川崎机器人故障代码主要用于指示机器人的不同运行问题和状态&#xff0c;帮助快速识别和解决这些问题。‌Kasawaki机械手故障代码通常以字母和数字的组合形式出现&#xff0c;其中字母代表故障的类型&#xff0c;而数字则是具体的代码编号。这些代码可以分为‌P‌代表操作错误…

05:创建逻辑软件元件库

1.创建逻辑软件元件库 点击 “编辑电参数” 1.1常规设置 1.2PCB封装 1.3门 1.4管脚 1.5检查元件 点击确定 1.6点击保存 2.处理重叠问题 2.1查看处理后的显示

《JavaEE进阶》----5.<SpringMVC②剩余基本操作(CookieSession)>

Cookie和Session简介。 Spring MVC的请求中 Cookie的设置和两种获取方式 Session的设置和三种获取方式。 三、&#xff08;接上文&#xff09;SpringMVC剩余基本操作 3.2postman请求 3.2.10 获取Cookie和Session 1.理解Cookie 我们知道HTTP协议自身是“无状态”协议。 &qu…

XtQuant接口概述,想用miniQMT做量化哪家券商支持?

XtQuant.XtData 行情模块 xtdata是xtquant库中提供行情相关数据的模块&#xff0c;本模块旨在提供精简直接的数据满足量化交易者的数据需求&#xff0c;作为python库的形式可以被灵活添加到各种策略脚本中。 主要提供行情数据&#xff08;历史和实时的K线和分笔&#xff09;、…

《黑神话悟空》:国产3A游戏的崛起与AI绘画技术的融合

一、游戏简介 近年来&#xff0c;国产3A游戏《黑神话悟空》以其精美的画面、丰富的剧情和独特的文化底蕴吸引了众多玩家的关注。这款游戏以中国古典名著《西游记》为背景&#xff0c;讲述了孙悟空历经磨难&#xff0c;最终成长为斗战胜佛的故事。在游戏制作过程中&#xff0c;开…

SpringBoot整合Mybatis,Junit (复现之前写的一个SSM项目)

引言 如下是之前写的一个SSM项目&#xff08;纯注解版&#xff09;&#xff0c;现在我们要把它改造成一个SpringBoot项目&#xff0c;以体现SpringBoot的方便。主要需要关注的文件已经用红框标出。 1.config文件夹里面的是Spring&#xff0c;SpringMvc&#xff0c;Mybatis的配…

zoom 会议 javascript 转录例子

一、启动server-to-server zoom api服务&#xff0c;用于创建会议&#xff0c;参考&#xff1a;如何使用Zoom API创建一个会议&#xff1f;-CSDN博客 二、启动meetingsdk-auth-endpoint服务&#xff0c;用于加入会议&#xff0c;参考&#xff1a;zoom 会议机器人web例子-CSDN博…

中国城市经济韧性数据集(2007-2022年)

数据来源&#xff1a;数据来自历年《中国城市统计NJ》、各省市《统计NJ》及《中国区域经济统计NJ》 时间范围&#xff1a;2007-2022年 数据范围&#xff1a;中国地级市样例数据&#xff1a; 包含内容&#xff1a; 全部内容下载链接&#xff08;原始数据计算代码最终数据&…

【binder】【android12】【2.servicemanager启动——全源码分析】

系列文章目录 可跳转到下面链接查看下表所有内容https://blog.csdn.net/handsomethefirst/article/details/138226266?spm1001.2014.3001.5501文章浏览阅读2次。系列文章大全https://blog.csdn.net/handsomethefirst/article/details/138226266?spm1001.2014.3001.5501 目录 …

CI/CD之Jenkins用于Linux系统的部署方式汇总

目录 一、前言 二、CI/CD的定义与核心原则 CI/CD在现代软件开发中的重要性 CI/CD与Jenkins的关系 三、Jenkins部署方式汇总 1. 独立服务器部署 &#xff08;1&#xff09;离线安装 &#xff08;2&#xff09;在线安装 2. Docker容器部署 3. Kubernetes集群部署 4. 云…

神经网络卷积层

一、卷积操作 对应位置相乘相加&#xff0c;最终组成一个新的矩阵&#xff0c;实现了降维。 二、代码 import torch import torchvision from torch import nn from torch.nn import Conv2d from torch.utils.data import DataLoaderdataset torchvision.datasets.CIFAR10(&…

2024最全网络安全工程师面试题(附答案),金九银十找工作必看!

吉祥知识星球http://mp.weixin.qq.com/s?__bizMzkwNjY1Mzc0Nw&mid2247485367&idx1&sn837891059c360ad60db7e9ac980a3321&chksmc0e47eebf793f7fdb8fcd7eed8ce29160cf79ba303b59858ba3a6660c6dac536774afb2a6330#rd 《网安面试指南》http://mp.weixin.qq.com/s…

浅析车辆类型检测算法实际应用车辆类型检测算法源码

随着交通运输和物流需求的不断增长&#xff0c;车辆类型检测的准确性和效率成为了一个关键问题。传统的检测方法往往依赖人工和基础的识别技术&#xff0c;面对日益复杂的交通环境&#xff0c;这些方法显得力不从心。幸运的是&#xff0c;智能算法的应用为这一问题带来了突破性…

JavaEE(servlet搭建)

Web开发概述 什么是Web? 所谓web开发,指的是从网页中向后端程序发送请求,与后端程序进行交互。流程图如下&#xff1a; Web服务器是指驻留与因特网上的某种类型计算机程序。 他可以向Web客户端提供文档也可以放置网站文件&#xff0c;让全世界浏览&#xff1b;它是一个容器…

基于协同过滤算法Spring Boot+Vue的图书商城系统

基于协同过滤算法的图书商城系统 1、系统流程图 网络书城购物系统由用户端&#xff0c;管理员端两大模块组成&#xff0c;各个模块下边又有许多小模块组成&#xff0c;每个模块的作用各不相同&#xff0c;但彼此之间又存在一定关系&#xff0c;通过分析上述模块之间的联系以及…

APP服务可用性监控与运维方案

一、引言 随着信息化业务的不断扩展&#xff0c;很多APP已关联众多外部服务&#xff0c;涵盖了互联网及内网环境。为确保用户体验&#xff0c;保障服务的高可用性成为运维团队的首要任务。本方案旨在建立一套全面的服务可用性监控体系&#xff0c;及时发现并解决潜在问题&#…

昇思AI框架实践1:安装MindSpoe和MindFormers

mindspore的python环境安装 项目需要安装MindSpoe和MindFormers两个软件包&#xff0c;最简单的安装方法是pip install安装&#xff1a; pip install mindspore2.2.0 mindformers-1.0.0 下面是详细的安装过程。 下载安装miniconda&#xff08;python环境&#xff09; mini…

python基础(13魔法方法介绍)

python系列文章目录 python基础&#xff08;01变量&数据类型&运算符&#xff09; python基础&#xff08;02序列共性&#xff09; python基础(03列表和元组) python基础&#xff08;04字符串&字典&#xff09; python基础&#xff08;05集合set&#xff09; pytho…

滚雪球学MyBatis-Plus(01):学前导读

&#x1f300;写在前面 我是bug菌&#xff0c;CSDN | 掘金 | InfoQ | 51CTO | 华为云 | 阿里云 | 腾讯云 等社区博客专家&#xff0c;C站博客之星Top30&#xff0c;华为云2023年度十佳博主&#xff0c;掘金多年度人气作者Top40&#xff0c;掘金等各大社区平台签约作者&#xff…