·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
这题是记忆化搜索。
因为高度的缘故所有走过的路一定不会再走一次，可以判断从每个点所能走的最远距离和已走路程是无关的，因而对于每一个点可以递归查询垓点可以走到的最远距离，在回溯前记录当前点能走到的最远距离即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int map[101][101];
int mdis[101][101];
int n,m;
int dfs(int x,int y) {
int ans=0;
if (mdis[x][y]) return mdis[x][y];
for (int i=0;i<4;i++) {
if (x+dx[i]>=0&&x+dx[i]<n&&y+dy[i]>=0&&y+dy[i]<m
&&map[x][y]>map[x+dx[i]][y+dy[i]]) {
ans=std::max(ans,dfs(x+dx[i],y+dy[i]));
}
}
mdis[x][y]=ans+1;
return mdis[x][y];
}
int main() {
int x=0,ans=0;
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
scanf("%d",&map[i][j]);
for (int i=0;i<n;i++)
for (int j=0;j<m;j++) {
x=dfs(i,j);
ans=std::max(x,ans);
}
printf("%d",ans);
}