题目描述
给定一个 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
C++ 代码
//类似于走迷宫
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=310;
int n,m;
int h[N][N];//网格滑雪场
int f[N][N];//状态转移式
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int dp(int i,int j){
if(f[i][j]!=-1){
return f[i][j];
}
f[i][j]=1;//情况最差只有自己一个
for(int k=0;k<4;k++){//遍历四个方向
int a=i+dx[k];
int b=j+dy[k];
if(a>=1 && a<=n && b>=1 && b<=m && h[a][b]<h[i][j]){
f[i][j]=max(f[i][j],dp(a,b)+1);//更新
//cout<<h<<"----";
}
}
return f[i][j];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>h[i][j];
}
}
memset(f,-1,sizeof f);
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<<"+++++";
}
}
cout<<res<<endl;
return 0;
}
/*int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>h[i][j];
}
}
memset(f,-1,sizeof f);
int res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=1;
for(int k=0;k<4;k++){
int a=i+dx[k];
int b=j+dy[k];
if(a>=1 && a<=n && b>=1 && b<=m && h[a][b]<h[i][j]){
f[i][j]=max(f[i][j],f[a][b]+1);
//f[a][b]必须是在f[i][j]之前已经求出来的,但a可以取i+1,不符合,所以这种方法不可取
//cout<<h<<"----";
}
}
res=max(res,f[i][j]);
//cout<<res<<"+++++";
}
}
cout<<res<<endl;
return 0;
}*/
python 代码
n,m=map(int,input().split())
h=[list(map(int,input().split())) for i in range(n)]
f=[[-1]*(m+1) for i in range(n+1)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def dp(i,j):
if f[i][j]!=-1: #如果状态f[i][j]已被更新,则返回
return f[i][j]
f[i][j]=1
for k in range(4):
a=i+dx[k]
b=j+dy[k]
if a>=0 and a<n and b>=0 and b<n and h[i][j]>h[a][b]:
f[i][j]=max(f[i][j],dp(a,b)+1)
return f[i][j]
res=0
for i in range(n):
for j in range(m):
res=max(res,dp(i,j))
print(res)