滑雪

题目链接：https://www.acwing.com/problem/content/903/

题目描述

给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

输入描述

第一行包含两个整数 R 和 C。
接下来 R 行，每行包含 C 个整数，表示完整的二维矩阵。

输出描述

输出一个整数，表示可完成的最长滑雪长度。
1≤R,C≤300,
0≤矩阵中整数≤10000

示例

输入

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出

25

分析

约定

记坐标为i,j的点的高度为h[i][j]

状态表示

f(i,j)表示从坐标为(i,j)的点开始的最大滑雪长度。

状态划分与计算

本题的状态划分比较简单，在点(i,j)有四个滑雪方向，分别是上下左右，分别求解选择最大的那个即可，因此状态转移方程如下：
f(i,j)=max(f(i+1,j),f(i,j+1),f(i-1,j),f(i,j-1))+1
注意这四个方向只有高度小于(i,j)的我们才去考虑，其余的直接忽略。

实现方式

本题，如果采用过去for循环的实现方式其实不太方便，求解任一点的解时我们需要已知相邻点的解，所以求解顺序应该是从高度低的点开始，以保证求解高度高的点时需要的数据已被求解，这就需要排序和存储排序的结果，比较麻烦，所以本题适合记忆化搜索的实现方式。
记忆化搜索采取递归的方式，不存在for循环实现的一些局限，不过要对搜索算法具有良好的基础，不然容易出错。
记忆化搜索的范式以及本题中存在一些易错点，详见代码。

AC代码

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const int N = 301;
int n, m;
int f[N][N];
int h[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int dp(int x, int y)
{
	if (f[x][y] != -1)	//-1代表该点未被计算过
		return f[x][y];

	f[x][y] = 1;	//计算一个点时一定要初始化 
					//如果四周没有高度比它高的点 不初始化就会出错

	for (int i = 0; i < 4; i++)
	{
		int a = x + dx[i];
		int b = y + dy[i];
		if (a >= 0 && a < n && b >= 0 && b < m && h[x][y] > h[a][b])	//边界判断
			f[x][y] = max(f[x][y], dp(a, b) + 1);
	}
	return f[x][y];
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> h[i][j];

	memset(f, -1, sizeof(f));	//-1代表该点未被计算过
	int res = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			res = max(res, dp(i, j));
		}
	}

	cout << res << endl;
	return 0;
}