[dfs搜索寻找矩阵中最长递减序列]魔法森林的秘密路径

news/2024/2/28 10:38:59

魔法森林的秘密路径

题目描述

在一个遥远的国度里,存在一个神秘的魔法森林,传说中森林深处隐藏着一个古老的宝藏。这个宝藏只能通过找到森林中最长的“递减魔法路径”来解锁。这个路径由一系列魔法石组成,每个魔法石刻有不同的数字,代表着它们的魔力强度。要找到宝藏,探险者必须沿着逐渐减弱魔力的石头前进,不能回头或走对角线。你是一位著名的探险家,被国王派遣来解开这个谜团。你的任务是找出最长的递减魔法路径,这样你就能找到隐藏的宝藏。

关于输入

魔法地图上的第一行包含两个整数,表示魔法森林区域的行数 m 和列数 n。
接下来的 m 行,每行包含 n 个整数,表示每块魔法石的魔力值。
数据保证 n,m ≤ 10

关于输出

作为一位智慧的探险家,你需要计算并输出最长递减魔法路径的长度。

例子输入
3 3
2 7 8
0 11 10
8 8 9
例子输出
6

解题分析

初看此题,是在一个二维数组里面找到最长的一个连续的递减数列(注意是严格递减,不要理解错例子了),例子输入中是11--10--8--7--2--0 所以长度为6。

其实我们可以利用DFS(深度优先搜索)的办法来解决本题,并且本题的数据量并不大,所以时间也在可接受的范围之内。

这个问题是一个典型的深度优先搜索(DFS)问题。你在上述代码中使用了深度优先搜索来解决最长递减路径的问题。

1. **初始化:**首先,定义一些变量。`m`和`n`是魔法森林的大小,`map`记录了每个位置魔石的魔力值,`maxPath`保存了当前找到的最长递减路径的长度,`walk`则是一个辅助矩阵,用于记录哪些位置已经走过。你还定义了两个数组`dx`和`dy`,分别记录了从当前位置向上、下、左、右四个方向移动时横坐标和纵坐标的变化量。

2. **深度优先搜索:**`dfs`函数是核心部分,它通过深度优先搜索寻找最长的递减路径。首先,函数会更新`maxPath`为`maxPath`和`step`中的较大值,`step`表示当前路径的长度。然后,函数会标记当前位置`(x, y)`为已经走过。接着,函数会试图向四个方向进行移动,如果新位置`(nx, ny)`在森林范围内,且其魔力值小于当前位置,且尚未被走过,那么函数就会向这个新位置移动,搜索长度为`step+1`的路径。最后,当函数回溯到当前位置时,根据深度优先搜索的特性,需要将`walk[nx][ny]`重置为0,以便其他路径可以再次经过这里。

3. **主函数:**在主函数里,首先读取魔法森林的大小和每个位置的魔力值,然后从每个位置出发,使用`dfs`函数寻找最长的递减路径。最后,输出找到的最长路径的长度`maxPath`。

这个代码的时间复杂度是O(4^(m*n)),因为最坏情况下要遍历所有可能的路径,而每个位置都有四个方向可以选择。而空间复杂度是O(m*n),因为需要使用一个二维数组来记录每个位置是否已经走过。

#include <iostream>
#include <cstring>
using namespace std;const int dx[]={0,1,-1,0},dy[]={-1,0,0,1};
int m,n,map[12][12],maxPath=0,walk[12][12]={0};void dfs(int x,int y,int step){maxPath=max(maxPath,step);walk[x][y]=1;for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(nx>=0 && nx<m && ny>=0 && ny<n && map[nx][ny]<map[x][y] && walk[nx][ny]==0){dfs(nx,ny,step+1);walk[nx][ny]=0;}}
}int main() {scanf("%d%d",&m,&n);for(int i=0;i<m;i++)for(int j=0;j<n;j++){scanf("%d",&map[i][j]);}for(int i=0;i<m;i++)for(int j=0;j<n;j++){memset(walk,0,sizeof(walk));dfs(i,j,1);}printf("%d\n",maxPath);return 0;
}


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

相关文章

网络爬虫之Ajax动态数据采集

动态数据采集 规则 有时候我们在用 requests 抓取页面的时候&#xff0c;得到的结果可能和在浏览器中看到的不一样&#xff0c;在浏览器中可以看到正常显示的页面教据&#xff0c;但是使用 requests 得到的结果并没有&#xff0c;这是因为requests 获取的都是原始的 HTML 文档…

【仿真】verilog调用c的reference module

作者&#xff1a;西南交通大学研究生导师邸志雄博士。 VPI: Verilog Prodecure Interface(VPI), 最开始也称作PLI 2.0, 一个主要面向C语言的接口. 可以让行为级别的Verilog代码调用C函数, 让C函数调用标准Verilog系统函数. 1 // adder.c2#include <vpi_user.h>34stat…

JavaWeb—html, css, javascript, dom,xml, tomcatservlet

文章目录 快捷键HTML**常用特殊字符替代:****标题****超链接标签****无序列表、有序列表****无序列表**:ul/li 基本语法**有序列表ol/li:****图像标签(img)**** 表格(table)标签****表格标签-跨行跨列表格****form(表单)标签介绍****表单form提交注意事项**div 标签p 标签sp…

MATLAB遗传算法工具箱的三种使用方法

MATLAB中有三种调用遗传算法的方式&#xff1a; 一、遗传算法的开源文件 下载“gatbx”压缩包文件&#xff0c;解压后&#xff0c;里面有多个.m文件&#xff0c;可以看到这些文件的编辑日期都是1998年&#xff0c;很古老了。 这些文件包含了遗传算法的基础操作&#xff0c;包含…

PSoc62™开发板之点亮LED

电路图 LED电路 板子有两个自主控制的LED&#xff0c;为绿色&#xff0c;通过上拉方式接入GPIO 按键引脚图 MCU_USER_LED1对应P0.0 MCU_USER_LED2对应P0.1 程序设计 以下程序用于循环控制两个LED灯亮灭&#xff0c;延时间隔为500ms #include <rtthread.h> #include…

第五章Netty第一节 粘包和半包

粘包与半包 粘包 现象&#xff1a;发送abc def,接受到abcdef 原因&#xff1a; 应用层&#xff1a;接收方ByteBuf设置太大&#xff08;Netty默认是1024&#xff09;传输层滑动窗口&#xff1a; 假设发送方256 bytes表示一个完整的报文&#xff0c;接收方的滑动窗口来不及处理…

随机问卷调查数据的处理(uniapp)

需求&#xff1a;问卷调查 1.返回的数据中包含单选、多选、多项文本框、单文本框、图片上传 2.需要对必填的选项进行校验 3.非必填的多项文本框内容 如果不填写 不提交 表单数据格式 res{"code": 0,"msg": null,"data": [{"executeDay&…

【Spring Security】分布式鉴权的使用

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是Java方文山&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;推荐给大家我的专栏《Spring Security》。&#x1f3af;&#x1f3af; …

【Linux笔记】系统信息

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;Linux学习 ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 命令 1. uname - 显示系统信息 2. hostname - 显示或设置系统主机名 3. top - 显示系统资源使用情况 4. df - 显示磁盘空间使用情…

2023年Top5搭建帮助中心工具集锦

随着企业知识管理的不断深化&#xff0c;帮助中心成为了一个越来越重要的组成部分。帮助中心是一个集成了企业知识、FAQ、常见问题解答、教程、使用指南等内容的在线平台&#xff0c;旨在为用户提供快速、准确的问题解答和自助服务。那么在这一年&#xff0c;有哪些搭建帮助中心…

ARM 点灯

.text .global _start _start: led1设置GPIOE时钟使能 RCC_MP_AHB4ENSETR[4]->1 0X50000A28LDR R0,0X50000A28 指定寄存器地址LDR R1,[R0] 将寄存器数值取出来放在R1中ORR R1,R1,#(0x1<<4) 将第4位设置为1STR R1,[R0] 将修改后的值写回去设置PE10为输出 GPIOE…

1161转进制(C语言)

一&#xff1a;题目 二&#xff1a;思路分析 1.首先该题目让我们使用递归求十进制转其他进制 2.其次&#xff0c;我们要知道十进制转换为其他进制怎么转换&#xff0c;以例题所给的数据为例 由此图可以看出&#xff0c;十进制转换为其他进制&#xff0c;是辗转相除法&#xf…

Android将自定义的SurfaceView保存为bitmap

正常将View保存为Bitmap的方法&#xff1a; private Bitmap getViewToBitmap(View view) { // layoutView(view);//创建Bitmap,最后一个参数代表图片的质量.Bitmap bitmap Bitmap.createBitmap(view.getWidth(), view.getHeight(), Bitmap.Config.ARGB_8888);if (bitma…

flutter 路由配置

get用法 进入新页面 Get.to(NextScreen());back回退操作 使用场景&#xff1a; 关闭Dialogs、SnackBars或者退出当前页面 Get.back(); off类似于replace操作 它会替拿当新页面换掉当前页面&#xff0c;并且新页面左上角没有返回按钮&#xff0c; Get.off(NextScreen()); off…

C++函数模板详解,轻松实现通用函数

C函数模板详解,轻松实现通用函数 函数模板 编写通用函数 您也可以为独立的函数编写模板。其语法与类模板类似。例如&#xff0c;您可以编写以下通用函数来在数组中查找一个值并返回其索引&#xff1a; static const size_t NOT_FOUND { static_cast<size_t>(-1) };te…

Win7如何修改MAC地址

MAC地址&#xff0c;又叫做物理地址、硬件地址&#xff0c;是用来定义网络设备的位置&#xff0c;一般情况下&#xff0c;MAC地址在网卡中是固定的&#xff0c;但不排除有人手动去修改自己的MAC地址。win7如何修改MAC地址?其实修改MAC地址的方法很简单&#xff0c;可以通过硬件…

人大金仓Kingbase数据库备份和还原

前言 最近在项目开发过程中&#xff0c;使用了国产数据库人大金仓&#xff08;即Kingbase数据库&#xff09;&#xff0c;在使用过过程中需要对数据库进行备份与还原&#xff0c;在此对相关的命令进行简单介绍&#xff0c;以备不时之需。 Linux环境下安装人大金仓可参考此篇文…

[RK-Linux] 解决RK3399 M.2 NVMe SSD根文件系统分区容量无法扩展到最大问题

延续《[RK-Linux] RK3399支持M.2 NVMe SSD启动》 在检查分区与挂载情况的时候,根文件系统分区容量是有问题的: root@buildroot:/# df -h Filesystem Size Used Avail Use% Mounted on /dev/root 692M 430M 209M 68% / devtmpfs 1.9G 8.0K 1.9G 1%…

SpringBootSQL监控

零、人在地球 一个成熟的生产环境会存在很多sql&#xff0c;测试环境不能完全复现出生产环境的情况。因此我们需要一些数据监控内容 一般用于监控&#xff1a; ①一些重点sql是否正常&#xff08;某些极端数据导致查询异常&#xff09; ②一些跑批任务的执行结果 ③一些表…

API 接口怎样设计才安全?

设计安全的API接口是确保应用程序和数据安全的重要方面之一。下面是一些设计安全的API接口的常见实践&#xff1a; 1. 身份验证和授权&#xff1a; 使用适当的身份验证机制&#xff0c;如OAuth、JWT或基本身份验证&#xff0c;以确保只有经过身份验证的用户可以访问API。实施…
最新文章