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

2023-12-23 21:33:58

魔法森林的秘密路径

题目描述

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

关于输入

魔法地图上的第一行包含两个整数,表示魔法森林区域的行数 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;
}

文章来源:https://blog.csdn.net/StudyingPanda/article/details/135172813
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。