题目:
本题关键字:记忆化搜索。
首先,这题为什么会想到记忆化?(知道的人直接跳过)
在dfs每种情况是,可能这个点之前已经搜过了,没必要再去搜索了,因此不如存储记住,就没必要再去dfs了。
本题的主要思路:
1.先去想dfs怎么做:
这题每个点出发有可能,所以我们每个点都要开始dfs,最后取他们的最大值。
dfs部分和类似的迷宫差不多,用两个数组表示4个方向:
dx[4]={0,0,1,-1}; dy[4]={1,-1,0,0};改变方向直接xx=x+dx[i] , yy=y+dy[i]
接下来判断这个方向是否在地图范围内,即
if(xx>0&&xx<=R&&yy>0&&yy<=C)当然还要判断这个点是否能滑到,也就是高度要前一个低:
if(a[xx][yy]<a[x][y])//a为高度
很明显,因为低的不可能滑向高的,所以我们不需要再开一个数组去记录这个点是否走过。
接下来,就要往四个方向搜索,取四个方向中距离最长的,然后+1,这就是这个点的结果了。
2.记忆化搜索怎么写
很显然,直接dfs会TLE。那么就需要记忆化来优化。
用s[i][j]表示从(i,j)点出发能走的最长距离。
每次搜索一次记忆一次即可。
下面给刚接触不怎么明白的人举例:(已经理解的人跳过)
由于样例不好讲我自己举例子:
3 3 1 1 3 2 3 4 1 1 1先去找(1,1)的最长距离,很明显为1
接着找(1,2)的最长距离,很明显为1
接着找(1,3)的最长距离,为2((1,3)->(1,2))
然后找(2,1)的最长距离,为2((2,1)->(1,1))
然后是(2,2)的最长距离,如果没有记忆化,那么搜索过程为:(2,2)->(2,1)->(1,1)
但是(2,1)之前已经搜过了,再去搜就是浪费时间,之前搜索已经知道(2,1)的值为2,那么搜索过程就是缩短为:(2,2)->(2,1),即为3
#include #include #include #include #define x first #define y second using namespace std; const int N = 110; typedef pair<int, int> PII; int ans; int n, m; int mp[N][N]; int dist[N][N]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int dfs(int s1, int s2) { if (dist[s1][s2]) return dist[s1][s2];//记忆化搜索 dist[s1][s2] = 1; for (int i = 0; i < 4; i ++ ) { int x = s1 + dx[i], y = s2 + dy[i]; if (x < 1 || x > n || y < 1 || y > m) continue; if (mp[x][y] >= mp[s1][s2]) continue; dfs(x, y); dist[s1][s2] = max(dist[s1][s2], dist[x][y] + 1); } return dist[s1][s2]; } 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 ++ ) ans = max(ans, dfs(i, j)); cout << ans << endl; }