十四届蓝桥杯STEMA考试Python真题试卷第二套第五题

news/2024/11/6 3:27:28/

来源:十四届蓝桥杯STEMA考试Python真题试卷第二套编程第五题
本题属于迷宫类问题,适合用DFS算法解决,解析中给出了Python中 map() 和列表推导式的应用技巧。最后介绍了DFS算法的两种常见实现方式——递归实现、栈实现,应用场景——迷宫类问题、图的连通性、树的遍历、拓朴排序、排列组合,以及主要优缺点。

题目描述

有一个 N*M 的矩阵,且矩阵中的每个方格都有一个整数(0≤整数≤100),小蓝需要按照以下要求从矩阵中找出一条最长的移动路线,且输出最长路线的长度(1 个方格为 1 个长度)。

要求:
1.小蓝可以从矩阵中任意一个方格开始向它的上、下、左、右相邻的任意一个方格移动,且移动的路线不能有交叉;
2.小蓝每次所要移动到的方格中的整数都要小于当前所在方格中的整数(如当前所在的方格中的整数为 3,那么可以移动到数字为 0,1,2 的格子里,不可以移动到数字为 3,4,5…的格子里);

例如:
N=3,M=3,矩阵方格如下:
在这里插入图片描述
最长路线为 4 -> 3 -> 2 -> 1,故路线长度为 4。

输入描述:
第一行输入两个正整数 N,M(1<N≤1000,1<M≤1000),N 表示矩阵的行数,M 表示矩阵的列数,两个正整数之间以一个空格隔开
第二行开始输入 N 行,每行包含 M 个整数(0≤每个整数≤100),表示每个方格中的整数,每个整数之间以一个空格隔开

输出描述:
输出一个整数,表示最长路线的长度

样例输入:

3 3
1 1 3
2 3 4
1 1 1

样例输出:

4

参考答案

python">def longestPath(matrix):rows, cols = len(matrix), len(matrix[0])max_length = 0def dfs(i, j, visited):# 1. 基本状态: 当前位置已经计入路径长度current_length = 1# 2. 定义四个移动方向: 上、下、左、右directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]# 3. 遍历每个可能的移动方向for di, dj in directions:# 计算新位置的坐标ni, nj = i + di, j + dj# 4. 检查移动的合法性if (0 <= ni < rows                      # 检查行是否越界and 0 <= nj < cols                  # 检查列是否越界and (ni, nj) not in visited         # 检查是否已访问and matrix[ni][nj] < matrix[i][j]   # 检查数字是否更小):# 5. 递归探索visited.add((ni, nj))   # 标记已访问# 计算包含当前位置的最长路径current_length = max(current_length, 1 + dfs(ni, nj, visited))visited.remove((ni, nj))            # 回溯,移除访问标记return current_length# 6. 遍历矩阵中的每个位置作为起点for i in range(rows):for j in range(cols):visited = {

http://www.ppmy.cn/news/1544704.html

相关文章

Redis-基本了解

一、Redis 初识 Redis 是⼀种基于键值对&#xff08;key-value&#xff09;的NoSQL数据库&#xff0c;与很多键值对数据库不同的是&#xff0c;Redis 中的值可以是由string&#xff08;字符串&#xff09;、hash&#xff08;哈希&#xff09;、list&#xff08;列表&#xff09…

Hms?: 1渗透测试

靶机&#xff1a;Hms?: 1 Hms?: 1 ~ VulnHub 攻击机&#xff1a;kail linux 2024 主机扫描阶段发现不了靶机&#xff0c;所以需要按DriftingBlues2一样手动配置网卡 1,将两台虚拟机网络连接都改为NAT模式&#xff0c;并查看靶机的MAC地址 2&#xff0c;攻击机上做主机扫描发现…

Docker:存储原理

Docker&#xff1a;存储原理 镜像联合文件系统overlay镜像存储结构容器存储结构 存储卷绑定挂载存储卷结构 镜像 联合文件系统 联合文件系统Union File System是一种分层&#xff0c;轻量且高效的文件系统。其将整个文件系统分为多个层&#xff0c;层与层之间进行覆盖&#x…

《机器人SLAM导航核心技术与实战》第1季:第10章_其他SLAM系统

视频讲解 【第1季】10.第10章_其他SLAM系统-视频讲解 【第1季】10.1.第10章_其他SLAM系统_RTABMAP算法-视频讲解 【第1季】10.2.第10章_其他SLAM系统_VINS算法-视频讲解 【第1季】10.3.第10章_其他SLAM系统_机器学习与SLAM-视频讲解 第1季&#xff1a;第10章_其他SLAM系统 …

Unity XR Interaction Toolkit 开发教程(3)快速配置交互:移动、抓取、UI交互【3.0以上版本】

获取完整课程以及答疑&#xff0c;工程文件下载&#xff1a; https://www.spatialxr.tech/ 视频试看链接&#xff1a; 3.快速配置交互&#xff1a;移动、抓取、UI交互【Unity XR Interaction Toolkit 跨平台开发教程】&#xff08;3.0以上版本&#xff09; 系列教程专栏&…

ARM64的Mac Node.js前置工作,nvm在线安装

1&#xff0c;通过 终端 ping raw.githubusercontent.com 获取到ip地址185.199.110.133 2&#xff0c;终端输入sudo vi /etc/hosts&#xff0c;打开hosts文件 3&#xff0c;在最后添加 185.199.110.133 raw.githubusercontent.com 保存后退出 3.1&#xff0c;清除环境 完全…

讲讲 kafka 维护消费状态跟踪的方法?

大家好&#xff0c;我是锋哥。今天分享关于【讲讲 kafka 维护消费状态跟踪的方法&#xff1f;】面试题&#xff1f;希望对大家有帮助&#xff1b; 讲讲 kafka 维护消费状态跟踪的方法&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 在 Kafka 中&#x…

最新整理:linux常见面试题库

一、说出10个以上的Linux命令,下面可以参考&#xff1a; 1、 创建文件&#xff1a;touch 2、 删除文件&#xff1a;rm(remove) 3、 查看文件&#xff1a;cat 4、 复制&#xff1a;cp(copy) 5、 创建文件夹&#xff1a;mkdir(make directory) 6、 剪切或者重命名&#xff…