题目: 滑雪
题意:
给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
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在给定矩阵中，一条可行的滑行轨迹为 24−17−2−1。
在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−1，沿途共经过 25 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
输入格式
第一行包含两个整数 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思路:
- 为什么要用记忆化搜索？我相信绝大部分人在接触BFS时已经做过这道题，递归广搜然后记录最长路径就可以了，但是现在题目的数据范围扩大了，暴力广搜就不再适用。
- 什么是记忆化搜索？我们会发现在广搜整个图时，有很多点其实已经搜过了，如果反复对其搜索会造成很大的时间浪费，所以我们可以用一个记忆化数组记录每个点是否已经搜索过，然后下次又走到这里时可以直接用。
- 再次感叹y总的代码习惯真的很优雅，不仅体现在格式上，更重要的是思路上。
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=310;
int f[N][N];//记忆化数组
int a[N][N];
int n,m;
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
int dp(int x,int y)
{
if(f[x][y])return f[x][y];
//当前格子最小是1
f[x][y]=1;
for(int i=0;i<4;++i)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]<a[x][y])
{
//为什么不能写成f[x][y]=dp(xx,yy)+1?因为f[x][y]可以由四个方向走过来，要保留最大的那个
f[x][y]=max(f[x][y],dp(xx,yy)+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>>a[i][j];
}
int res=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
res=max(res,dp(i,j));
}
}
cout<<res;
return 0;
}
