#include <iostream>
#include <algorithm>
using namespace std;
int h[100][100];
int res[100][100];
int ski(int r,int c,int r0,int c0){//r,c为起点,最多的方法数
if(res[r][c]!=-1){//证明已经计算过了
return res[r][c];
}else{
res[r][c]=1;
//找到上下左右中最大的元素的位置
int rm=-1;
if(c-1>=0&&h[r][c-1]<h[r][c]){//可行路线
rm=1;
ski(r,c-1,r0,c0);
}
if(c<c0-1&&h[r][c+1]<h[r][c]){//可行路线
rm=1;
ski(r,c+1,r0,c0);
}
if(r-1>=0&&h[r-1][c]<h[r][c]){//可行路线
rm=1;
ski(r-1,c,r0,c0);
}
if(r<r0-1&&h[r+1][c]<h[r][c]){//可行路线
rm=1;
ski(r+1,c,r0,c0);
}
if(rm==-1){//周围没有比他还要小的
return res[r][c];
}else{//在某个位置找到了比它更小的
res[r][c]+=max(max(res[r-1][c],res[r+1][c]),max(res[r][c+1],res[r][c-1]));
return res[r][c];
}
}
}
int main(){
int r,c,i,j;
scanf("%d %d",&r,&c);
for(i=0;i<r;i++){
for(j=0;j<c;j++){
scanf("%d",&h[i][j]);
}
}
for(i=0;i<r;i++){
for(j=0;j<c;j++){
res[i][j]=-1;
}
}
int jieguo=1;
for(i=0;i<r;i++){
for(j=0;j<c;j++){
ski(i,j,r,c);
}
}
for(i=0;i<r;i++){//寻找这个二维数组中的最大值
int tmp=*max_element(res[i],res[i]+c-1);
if(tmp>jieguo){
jieguo=tmp;
}
}
printf("%d",jieguo);
return 0;
}
采用的是记忆化递归算法,思路就是递归遍历每一个点的上下左右,但是只有50分。
希望大佬能够给指出错误,另外祝大家国庆节快乐!