考虑记忆化DFS。将每个点都搜索出可经过的最大高度,再算出每个点的最大值。
一定要将它的最长高度来自它的上下左右四个边的最长路+1。
如果它的高度小于它相邻的四个点(i+1,j)(i-1,j)(i,j-1)(i+1),就可以滑向[i][j]。将它们的最长路径求出来,即为答案。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int mp[1000][1000],dp[1000][1000];
int n,m;
int sum=0;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool in(int x, int y){
return 0<x && x <= n && 0<y && y <= m;
}
int dfs(int x, int y){
if(dp[x][y] && x!=1 && y!=1){
return dp[x][y];
}
for(int i = 0; i<=4;i++){
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(in(tx, ty) && mp[tx][ty]>mp[x][y]){
dp[x][y] = max(dfs(tx, ty)+1,dp[x][y]);
}
}
if(!dp[x][y]){
dp[x][y] = 1;
}
return dp[x][y];
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> mp[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
sum = max(dfs(i,j),sum);
}
}
cout << sum;
return 0;
}
# %%%