OD C卷 - 园区参观路径

园区参观路径(100)

  • 有一个矩形园区,从左上角走到右下角,只能向右、向下走;
  • 共有多少条不同的参观路径;
    在这里插入图片描述

输入描述:
第一行输入长度、宽度
后续每一行表示 对应位置是否可以参观,0可以,1不可以
输出描述:
不同路径的数量

示例1
输入:
3 3
0 0 0
0 1 0
0 0 0
输出:
2

示例2
输入:
4 3
0 1 0
0 0 0
0 0 1
1 0 0
输出:
2

思路:

  • 深度优先,能走到终点,则max_path += 1

row, col = list(map(int, input().strip().split()))matrix = []
for i in range(row):matrix.append(list(map(int, input().strip().split())))# 两个方向
directs = [0, 1, 0]
max_paths = 0def dfs(x, y):global max_pathsd = 0while d < 2:xx = x + directs[d]yy = y + directs[d+1]if xx < row and yy < col and matrix[xx][yy] == 0: # 可以走 (位置可以重复参观)if xx == row - 1 and yy == col - 1:max_paths += 1returnelse:dfs(xx, yy)# 位置无效或者不能参观,则调转方向d += 1returndfs(0, 0)
print(max_paths)
  • 动态规划
    • matrix 表示格子数据
    • dp 二维数组表示到达每个格子时的不同路径数,当第i行,第j列的格子即matrix[i-1][j-1]位置为0时,则可以从上边、左边走过来,对应的路径数为dp[i][j] = dp[i-1][j] + dp[i][j-1]
    • 最后dp[row][col] 即为到达终点的不同路径数

from typing import Listdef func(matrix):global row, col# 第 i 行 j列 在dp中即为索引, 在matrix中 i-1, j-1 为索引# 二维数组 dp[i][j] 表示 matrix中从 (0, 0)起始点 到 (i - 1, j - 1)终点 的不同路径数,# 初始化均为 0dp: List[List[int]] = [[0 for _ in range(col+1)] for _ in range(row + 1)]# 为了将matrix[0][0] 起始点设置为 1 (起始点可以从上边、左边走过来)dp[0][1] = 1# 遍历当前要走到的格子下标 (i, j)for i in range(1, row + 1):  # 要走的第i行  (i-1才为索引)for j in range(1, col + 1):# 如果当前格子为0,则可以从上边和左边走过来if matrix[i - 1][j - 1] == 0:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]# dp[row][col] 就是从 (0, 0) 到 (m - 1, n - 1) 的不同路径数return dp[row][col]row, col = [int(x) for x in input().strip().split()]
matrix = []
for i in range(row):matrix.append([int(x) for x in input().strip().split()])print(func(matrix))

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

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

相关文章

poetry配置镜像

1.简介 poetry 是一个包管理和打包的工具。 在 Python 中&#xff0c;对于初学者来说&#xff0c;打包系统和依赖管理是非常复杂和难懂的。即使对于经验丰富的开发者&#xff0c;一个项目总是要同时创建多个文件&#xff1a; setup.py ,requirements.txt,setup.cfg , MANIFES…

【数据结构与算法】十大经典排序算法深度解析:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序、桶排序、基数排序

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《数据结构与算法》 期待您的关注 ​ 目录 引言 一、排序算法概述 排序算法简介 排序算法的分类 性能指标 二、十大排序算法…

Unity Rigidbody 踩坑记录

1&#xff1a;两个带有刚体的物体碰撞会一直不停的弹 把被动受力的刚提的 Freeze Position 的勾选 去掉&#xff08;碰到过一次&#xff0c;有一种受力无法释放又返回给目标的 所以一直弹跳的感觉&#xff09; 2&#xff1a;子物体 和父物体 都有刚体的情况下 子物体 Freeze R…

zdpy+vue3+onlyoffice文档系统实战上课笔记 20240805

上次 上次计划 1、最近文档表格完善 2、实现登录功能 3、新建文件&#xff0c;复制文件&#xff0c;删除文件 4、其他 目前任务&#xff1a;最近文档表格完善 1、在名称前面&#xff0c;渲染这个文档的图标 2、大小的基本的单位是kb&#xff0c;超过1024kb则换成mb&#xff0…

Java | Leetcode Java题解之第318题最大单词长度乘积

题目&#xff1a; 题解&#xff1a; class Solution {public int maxProduct(String[] words) {Map<Integer, Integer> map new HashMap<Integer, Integer>();int length words.length;for (int i 0; i < length; i) {int mask 0;String word words[i];in…

Mysql中事务的读一致性问题,以及如何用MVCC解决

事务四大特性的实现&#xff1a; 原子性事务具有回滚的能力&#xff0c;InnoDB引擎使用undo log日志表来进行回滚操作。 持久性InnoDB引擎使用redo log日志表来保证数据的持久性。 事务的隔离性产生的问题&#xff1a; 脏读&#xff1a;一个事务读取到了另一个事务未提交的数…

Linux系统驱动(五)

文章目录 一、实现机制二、字符设备驱动分布实现流程三、添加自己的系统调用函数1. 找到系统调用文件2. 找到 一、实现机制 应用层 vfs层 驱动层 字符设备按照字节流顺序访问&#xff0c;但是实际它提供了无序访问的功能 vi -t sys_open 内核中通过inode号可以唯一的找到一…

请转告HPC计算AI计算单位,选对存储事半功倍

U.2 NVMe全闪混合统一存储GS 5000U是Infortrend产品中一款高性能机型。得益于搭载强劲的第五代IntelXeon处理器&#xff0c;以及支持PCIe 5.0、NVMe-oF、100GbE等多种特点&#xff0c;GS 5000U单台块级性能可达50 GB/s的读、20 GB/s的写&#xff0c;以及1300K的IOPS&#xff1b…

Xshell安装图文

1.下载 通过百度网盘分享的文件&#xff1a;Xshell安装图文 链接&#xff1a;https://pan.baidu.com/s/1k4ShbhUVQmdxpM9H8UYOSQ 提取码&#xff1a;kdxz --来自百度网盘超级会员V3的分享 2.安装 3.连接与使用 见下载

论文辅导 | 基于二次分解和BO-BiLSTM组合模型采煤工作面瓦斯涌出量预测方法研究

辅导文章 模型描述 结合变分模态分解&#xff08;VMD&#xff09;、自适应噪声完备经验模态分解&#xff08;CEEMDAN&#xff09;、贝叶斯优化算法&#xff08;BO&#xff09;和双向长短期记忆神经网络&#xff08;BiLSTM&#xff09;这4种时间序列处理方法&#xff0c;建立了…

AllReduce通信库;Reduce+LayerNorm+Broadcast 算子;LayerNorm(层归一化)和Broadcast(广播)操作;

目录 AllReduce通信库 一、定义与作用 二、常见AllReduce通信库 三、AllReduce通信算法 四、总结 Reduce+LayerNorm+Broadcast 算子 1. Reduce 算子 2. LayerNorm 算子 3. Broadcast 算子 组合作用 LayerNorm(层归一化)和Broadcast(广播)操作 提出的创新方案解析 优点与潜在…

项目实战_图书管理系统(简易版)

你能学到什么 一个简单的项目——图书管理系统&#xff08;浏览器&#xff1a;谷歌&#xff09;基础版我们只做两个功能&#xff08;因为其它的功能涉及的会比较多&#xff0c;索性就放在升级版里了&#xff0c;基础版先入个门&#xff09; 登录: ⽤⼾输⼊账号,密码完成登录功…

登录相关功能的优化【JWT令牌+拦截器+跨域】

登录相关功能的优化 登录后显示当前登录用户el-dropdown: Element - The worlds most popular Vue UI framework <el-dropdown style"float: right; height: 60px; line-height: 60px"><span class"el-dropdown-link" style"color: white;…

音视频开发 sdl库

介绍 SDL (Simple DirectMedia Layer) 是一个跨平台的开源多媒体库,它提供了底层访问多种硬件的接口,如音频、视频、输入设备等。它主要用于游戏开发,但也可用于其他类型的多媒体应用程序。下面是 SDL 的一些主要特点: 跨平台性: SDL 支持多种操作系统,包括 Windows、macOS、L…

HashMap中 put()方法的流程、扩容的思路(源码分析~)

文章目录 put() 方法的流程扩容流程为什么它会按照2的幂次方进行扩容呢&#xff1f; put() 方法的流程 下面我们通过分析源码来总结一下 put() 方法的流程 扩容流程 根据上图的分析&#xff0c;就可以总结出 HashMap 的扩容流程&#xff1a; 在插入元素时&#xff0c;会先…

C# 设计模式之原型模式

总目录 前言 在软件系统中&#xff0c;当创建一个类的实例的过程很昂贵或很复杂&#xff0c;并且我们需要创建多个这样类的实例时&#xff0c;如果我们用new操作符去创建这样的类实例&#xff0c;这未免会增加创建类的复杂度和耗费更多的内存空间&#xff0c;因为这样在内存中…

复现一下最近学习的漏洞(sqlab 1-10)

第一个问题&#xff1a;为什么不能用#来闭合单引号呢&#xff1f; 在进行URL地址栏传参的时候&#xff0c;是有一套编码规范的。他不会编码英文、数字和某些符号。但是#它会进行编码。也就是%23。&#xff08;先转ascii码&#xff0c;然后再转十六进制&#xff0c;之后加上%就是…

软甲测试定义和分类

软件测试定义 使用人工和自动手段来运行或测试某个系统的过程&#xff0c;其目的在于检验他是否满足规定的需求或弄清预期结果与实际结果之间的差别 软件测试目的 为了发现程序存在的代码或业务逻辑错误 – 第一优先级发现错误为了检验产品是否符合用户需求 – 跟用户要求实…

函数实例讲解(四)

文章目录 提取不重复值&#xff08;INDEX、MATCH、COUNTIF&#xff09;1、INDEX2、MATCH3、COUNTIF 提取不重复的值的经典套路&#xff08;LARGE、SMALL、ROW&#xff09;1、ROW2、LARGE3、SMALL&#xff09; 制作Excel动态查询表四舍五入函数(ROUND、ROUNDUP、ROUNDDOWN&#…

20240806 每日AI必读资讯

英伟达最强AI芯片曝重大设计缺陷&#xff0c;中国特供版意外曝光&#xff01; - 由于Blackwell GPU的设计缺陷&#xff0c;英伟达发货时间不得不推迟3个月 - GB200包含了2个Blackwell GPU和1个Grace CPU。问题出在连接2个Blackwell GPU的关键电路 - 意味着对于Meta、谷歌、微…