[SHOI2002] 滑雪
题目描述
Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
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$－$16$－$1$（从 $24$ 开始，在 $1$ 结束）。当然 $25$－$24$－$23$－$\ldots$－$3$－$2$－$1$ 更长。事实上，这是最长的一条。
输入格式
输入的第一行为表示区域的二维数组的行数 $R$ 和列数 $C$。下面是 $R$ 行，每行有 $C$ 个数，代表高度(两个数字之间用 $1$ 个空格间隔)。
输出格式
输出区域中最长滑坡的长度。
样例 #1
样例输入 #1
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
样例输出 #1
25
提示
对于 $100%$ 的数据，$1\leq R,C\leq 100$。
思考：
状态表示：
有几个方向，
-
$f_i$表示以高度为 $i$ 的节点开始最多能滑多远
-
$f_{i,j}$表示从节点$ w_{i,j} $开始能滑多远
如果是方向$1$就要考虑高度相同的情况。
如果是方向$2$要考虑效率问题。
似乎都可以记忆化搜索？
考虑从左上角开始往右下角搜索，这样搜索到的节点就可以记忆化
也许$DFS$记忆化搜索是正解，方案一不好记忆化（如果高度相同），那么先方案二
记忆化思路：
$DFS$函数的返回值是从当前值开始走，最多能走多少步
1.如果已经被搜索，那么直接返回
2.如果还没有被搜索，那么$f_{i,j}$就等于向下$DFS$的步数再加一（自己）
3.如果该点不能向四周移动了，那么返回$1$（自己这一步）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 105;
int h[N][N] , f[N][N];
//f[i][j]保存从(i,j)开始的方案数
int column[4] = {1 , 0 , -1 , 0} , row[4] = {0 , -1 , 0 , 1};
//向四个方向的向量
int dfs(int x , int y){
//从节点(x,y)开始DFS
if(f[x][y] != -1)
return f[x][y];
//记忆化搜索
bool able = false;
//如果可以走
for(int i = 0 ; i < 4 ; i++) {
int u = x + row[i] , v = y + column[i];
if(h[u][v] < h[x][y]){ //高度减小
able = true ;
f[x][y] = max(f[x][y] , 1 + dfs(u , v));
}
}
if( !able )
f[x][y] = 1;
return f[x][y];
}
int main(){
int R , C;
scanf("%d%d" , &R , &C);
memset(f , -1 , sizeof f);
memset(h , 0x7f , sizeof h);
//通过建立极高的墙使得滑雪者不能通过
for(int i = 1 ; i <= R ; i++)
for(int j = 1 ; j <= C ; j++)
scanf("%d" , & h[i][j]);
int ans = -1;
for(int i = 1 ; i <= R ; i++)
for(int j = 1 ; j <= C ; j++)
ans = max(ans , dfs(i , j));
printf("%d\n" , ans);
return 0;
}