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

相关文章

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

MiniGPT-3D, 首个高效的3D点云大语言模型,仅需一张RTX3090显卡,训练一天时间,已开源

项目主页:https://tangyuan96.github.io/minigpt_3d_project_page/ 代码:https://github.com/TangYuan96/MiniGPT-3D 论文:https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA,被ACM MM2024接收,只拥有47.8M的可训练参数,在一张RTX

如何确定 Go 语言中 HTTP 连接池的最佳参数?

确定 Go 语言中 HTTP 连接池的最佳参数可以通过以下几种方式: 一、分析应用场景和需求 并发请求量: 确定应用程序在特定时间段内可能同时发起的 HTTP 请求数量。如果并发请求量很高,需要设置较大的连接池参数以满足需求。例如,对于一个高并发的 Web 服务,可能同时有数百个请求在处理,此时需要较大的连接池大小。可以通过压力测试工具模拟高并发场景,观察系统在不同并发请求下的性能表现,从而

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop