自己怎么开网站备案,我想网,广告推广语,营销方案怎么写魔法森林的秘密路径
题目描述
在一个遥远的国度里#xff0c;存在一个神秘的魔法森林#xff0c;传说中森林深处隐藏着一个古老的宝藏。这个宝藏只能通过找到森林中最长的“递减魔法路径”来解锁。这个路径由一系列魔法石组成#xff0c;每个魔法石刻有不同的数字#xf…魔法森林的秘密路径
题目描述
在一个遥远的国度里存在一个神秘的魔法森林传说中森林深处隐藏着一个古老的宝藏。这个宝藏只能通过找到森林中最长的“递减魔法路径”来解锁。这个路径由一系列魔法石组成每个魔法石刻有不同的数字代表着它们的魔力强度。要找到宝藏探险者必须沿着逐渐减弱魔力的石头前进不能回头或走对角线。你是一位著名的探险家被国王派遣来解开这个谜团。你的任务是找出最长的递减魔法路径这样你就能找到隐藏的宝藏。
关于输入
魔法地图上的第一行包含两个整数表示魔法森林区域的行数 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)在森林范围内且其魔力值小于当前位置且尚未被走过那么函数就会向这个新位置移动搜索长度为step1的路径。最后当函数回溯到当前位置时根据深度优先搜索的特性需要将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],maxPath0,walk[12][12]{0};void dfs(int x,int y,int step){maxPathmax(maxPath,step);walk[x][y]1;for(int i0;i4;i){int nxxdx[i],nyydy[i];if(nx0 nxm ny0 nyn map[nx][ny]map[x][y] walk[nx][ny]0){dfs(nx,ny,step1);walk[nx][ny]0;}}
}int main() {scanf(%d%d,m,n);for(int i0;im;i)for(int j0;jn;j){scanf(%d,map[i][j]);}for(int i0;im;i)for(int j0;jn;j){memset(walk,0,sizeof(walk));dfs(i,j,1);}printf(%d\n,maxPath);return 0;
}
