题目描述
给定一个 R 行 C 列的矩阵,表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发,每次可以向上下左右任意一个方向滑动一个单位距离。
当然,一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
样例
输入样例:
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
#include<iostream>
#include<cstring>
using namespace std;
const int N=310;
int f[N][N],h[N][N];
int r,c;
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
int dp(int x,int y)
{
if(f[x][y]!=-1)return f[x][y];//如果这个点存在最长路径了,就不用dp了
f[x][y]=1;
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a>0&&a<=r&&b>0&&b<=c&&h[a][b]<h[x][y])
f[x][y]=max(f[x][y],dp(a,b)+1);
}
return f[x][y];
}
int main()
{
cin>>r>>c;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
cin>>h[i][j];
memset(f,-1,sizeof(f));
int res=0;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
res=max(res,dp(i,j));//枚举每个点为起点的情况
cout<<res<<endl;
return 0;
}