题目描述

给定一个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

算法1

(dfs+记忆化)

#include<bits/stdc++.h>
using namespace std;
int f[350][350]; //记录从（x，y）点能滑雪的最长距离 
int a[350][350];//读入滑雪场的数据 
int n,m;
int dx[]={-1,0,1,0};//改变方位的 
int dy[]={0,-1,0,1};
int dfs(int x,int y)
{
    if(f[x][y]) return f[x][y];//如果已经记录过了，就不用再算了 
    f[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i];//到下一个点 
        int yy=y+dy[i];
        if(xx>=1&&xx<=n&&yy>=1&&y<=m&&a[x][y]>a[xx][yy])//点在范围内，且此点高度，比刚才的点矮就滑过去 
        {
            f[x][y]=max(f[x][y],dfs(xx,yy)+1);//比较大小，取出最大的 
        }                                       //+1，是因为如果到从两个点的滑雪距离一样的话，再滑一步，就滑到x，y这个点了，所以+1 
    }
    return f[x][y];//返回最终值 
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            res=max(res,dfs(i,j));
        }
    }
    printf("%d\n",res);
    return 0;
}