计科余定成

用户名：dotcpp0598358

访问量：15792

签　名：

孙蕾，我好喜欢你啊，为了你我要把键盘敲烂!!!

等　　级
排　　名	41
经　　验	13047
参赛次数	1
文章发表	69
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

我是余定成

TA的其他文章

刻录光盘（c++）
浏览：66

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

滑雪（搜索）

　　作者: 计科余定成　　　　发表时间：2023-03-05 15:09:27 浏览：55　|　评论：0　

原题链接：信息学奥赛一本通T1280-滑雪

解题思路：记忆化搜索
```cpp
·这道题需要求出二维数组中最长的下降路径，可以使用记忆化搜索来解决。
·我们可以定义一个二维数组f[x][y]表示从坐标(x,y)出发所能到达的最长下降路径，通过深度优先搜索的方式计算出每个位置所能到达的最长下降路径。
·在搜索过程中，我们可以先判断f[x][y]是否已经被计算出来，如果已经被计算出来，则直接返回f[x][y]，否则计算出f[x][y]的值。对于(x,y)位置，我们需要分别往上下左右四个方向进行搜索，如果搜索到的位置比当前位置高，则继续往下搜索，否则停止搜索。
·在计算出f[x][y]的值之后，更新答案ans=max(ans,f[x][y])。
·最后，输出ans即可。
```
注意事项：
```cpp
·在搜索过程中需要注意边界的问题，要判断搜索到的位置是否在数组范围内。
·在更新f[x][y]的值时，需要取max，因为当前位置可以从四个方向中的任意一个位置到达，所以需要取最大值。
```
参考代码：
```cpp
#include<bits/stdc++.h>
using namespace std;

#define ll long long

int mp[105][105] = {}; // mp数组保存输入的高度信息
int f[105][105] = {}; // f数组保存当前点所在的最长滑坡长度
int dx[4] = {0, 0, 1, -1}; // dx和dy分别表示向上、向下、向左、向右的方向变化
int dy[4] = {1, -1, 0, 0};
int n, m; // n和m分别为矩阵的行数和列数

// dfs函数用来遍历每个点，并返回当前点所在的最长滑坡长度
int dfs(int x, int y) {
	if (f[x][y]) return f[x][y]; // 如果f[x][y]已经被计算过了，则直接返回f[x][y]的值
	if (x < 1 || x > n || y < 1 || y > m) return f[x][y]; // 如果当前点超出矩阵范围，则直接返回f[x][y]的值
	f[x][y] = 1; // 将f[x][y]初始化为1，即自己本身算作一个长度
	int tx, ty;
	for (int i = 0; i < 4; i++) { // 遍历当前点的上下左右四个方向
		tx = x + dx[i];
		ty = y + dy[i];
		if (mp[tx][ty] > mp[x][y]) { // 如果下一个点的高度比当前点高
			dfs(tx, ty); // 递归求解下一个点的最长滑坡长度
			f[x][y] = max(f[x][y], f[tx][ty] + 1); // 更新当前点的最长滑坡长度
		}
	}
	return f[x][y]; // 返回当前点所在的最长滑坡长度
}

int main() {
	cin >> n >> m; // 输入矩阵的行数和列数
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mp[i][j]; // 输入每个点的高度信息
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dfs(i, j); // 遍历每个点，求解最长滑坡长度
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ans = max(ans, f[i][j]); // 更新最长滑坡长度的值
		}
	}
	cout << ans; // 输出最长滑坡长度的值
	return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

程序员的表白（C语言代码）

wu-理财计划（C++代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

滑雪（搜索）

评论区

精彩推荐

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

1197求助

众数问题（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

字符串的修改（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （Java代码）

C语言程序设计教程（第三版）课后习题8.2 （C++代码）

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

程序员的表白 （C语言代码）

wu-理财计划 （C++代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

滑雪（搜索）

评论区

精彩推荐

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

1197求助

众数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

字符串的修改 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （Java代码）

C语言程序设计教程（第三版）课后习题8.2 （C++代码）

程序员的表白（C语言代码）

wu-理财计划（C++代码）

　　评论区

众数问题（C语言代码）

字符串的修改（C语言代码）