本题设dp[i][j]代表从(i,j)这个点出发能够走到的最大距离。但是由于他的上下左右其实也没有被确定,在这里使用记忆化搜索如果上下左右某处没有被确定的话就递归去搜索,如果搜索到的某处为其上下左右的最小值的话就直接返回,如果已经搜索过了也直接返回。此外还要做边界的判断。
将每一个点都进行一次记忆化搜索取其最大值就行。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100+10;
int n, m;
int a[maxn][maxn];
int dp[maxn][maxn];
//记忆化搜索。
int calc(int i, int j) {
int num = 0;
//搜过了不用再搜了。
if (dp[i][j]!=0) return dp[i][j];
// if (i<=0||i>n||j<=0||j>m) return 0;
dp[i][j] = 1;
if (a[i-1][j]<a[i][j]&&(i-1)&&j) {
dp[i][j] = max(dp[i][j], calc(i-1, j)+1);
}
if (a[i][j-1]<a[i][j]&&i&&(j-1)) {
dp[i][j] = max(dp[i][j], calc(i, j-1)+1);
}
if (a[i+1][j]<a[i][j]&&(i+1)&&j) {
dp[i][j] = max(dp[i][j], calc(i+1, j)+1);
}
if (a[i][j+1]<a[i][j]&&i&&(j+1)) {
dp[i][j] = max(dp[i][j], calc(i, j+1)+1);
}
return dp[i][j];
}
int main() {
cin>>n>>m;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
cin>>a[i][j];
}
}
int ans = 0;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
ans = max(calc(i, j), ans);
}
}
cout<<ans;
return 0;
}

京公网安备 11010502036488号