Family Day/园区参观路径(C语言)

2024-02-23 01:04

本文主要是介绍Family Day/园区参观路径(C语言),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

园区某部门举办了Family Day,邀请员工及其家属参加;
将公司园区视为一个矩形,起始园区设置在左上角,终点园区设置在右下角;
家属参观园区时,只能向右和向下园区前进,求从起始园区到终点园区会有多少条不同的参观路径。
image-20231204211222633

输入描述

第一行为园区的长和宽;
后面每一行表示该园区是否可以参观,0表示可以参观,1表示不能参观

输出描述

输出为不同的路径数量

用例

输入

3 3
0 0 0
0 1 0
0 0 0

输出

2

思路

动态规划(Dynamic Programming, DP)是一种在数学、管理科学、计算机科学、经济学等多领域中用于求解最优化问题的算法思想。它主要针对具有重叠子问题和最优子结构的问题,通过将复杂问题分解为相对简单的子问题,并存储并重用这些子问题的解以减少重复计算,从而得到原问题的最优解或所有可能解的数量。

在本题中,我们要求的是从园区左上角到右下角有多少种不同的参观路径。这个问题符合动态规划的应用场景:

  1. 重叠子问题:在计算到达某个园区的不同路径数量时,会涉及到到达其上方和左侧园区的路径数量。例如,在计算 (i, j) 园区的路径数时,需要知道 (i-1, j)(i, j-1) 的路径数,这意味着当我们计算其他位置时,可能会再次用到这些信息。

  2. 最优子结构:问题的最优解可以通过组合其子问题的最优解来构造。具体来说,(i, j) 位置的路径数量等于其上方 (i-1, j) 和左侧 (i, j-1) 两个位置路径数量之和,前提是当前位置是可以参观的。

因此,我们可以采用一个二维数组 dp 来保存每个园区的路径数量,初始化时,左上角园区(起点)的路径数量为1,然后按照从上到下、从左到右的顺序遍历整个园区,根据每个园区是否可参观以及与相邻园区的关系来递推计算每个园区的路径数量。最终,右下角园区(终点)的路径数量即为所求答案。

代码

#include <stdio.h>
#include <stdlib.h>int main() {// 读取园区的行数(高)和列数(宽)int m, n;scanf("%d %d", &m, &n);// 初始化一个m×n的二维数组map,用于存储每个园区是否可以参观int map[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 读取输入数据,0表示园区可参观,1表示不可参观scanf("%d", &map[i][j]);}}// 初始化一个与map同样大小的二维数组dp,用于动态规划计算不同路径数量int dp[m][n];// 动态规划遍历整个园区for (int i = 0; i < m; i++) {     // 遍历行for (int j = 0; j < n; j++) { // 遍历列// 当前园区可参观时if (map[i][j] == 0) {// 如果在起点(0, 0),则只有一种路径(自身)if (i == 0 && j == 0) {dp[i][j] = 1;}// 如果在第一列(即只有向右的移动),则当前园区的路径数等于上一行同列园区的路径数else if (i == 0) {dp[i][j] = dp[i][j - 1];}// 如果在第一行(即只有向下的移动),则当前园区的路径数等于上一列同行园区的路径数else if (j == 0) {dp[i][j] = dp[i - 1][j];}// 对于其他园区,其路径数等于上一行同列园区路径数加上上一列同行园区路径数else {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}// 当前园区不可参观时,路径数为0else {dp[i][j] = 0;}}}// 输出从起始园区到终点园区的不同参观路径数量printf("%d\n", dp[m - 1][n - 1]); // 结束位置是(m-1, n-1),即右下角园区return 0; // 程序执行成功返回0
}

这段代码通过动态规划的方法解决了给定问题。它首先读取矩形园区的大小以及每个园区的可访问性,然后使用二维数组dp来记录从左上角到达每个园区的不同路径数量,并根据当前位置相对于上一行或上一列园区的关系来递推计算路径数。最后输出从左上角到右下角的路径总数。

文章目录

    • 题目描述
    • 输入描述
    • 输出描述
    • 用例
    • 思路
    • 代码

这篇关于Family Day/园区参观路径(C语言)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/737060

相关文章

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使