–
类似问题:大西洋太平洋水流问题
算法
(记忆化搜索)
引用作者小呆呆 的一句话:
本来是一个dfs的过程,遍历所有的位置,找到从当前位置往下走的最大路径,再取最大值,可是这样做会有很多重复的位置被重新计算过,因此可以利用空间换时间的思想,把遍历过的位置往下走的路径的最大值进行记录,这就是记忆化搜索
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 310;
int n,m;
int g[N][N];
int f[N][N];
int dx[4] = {0,1,0,-1} ,dy[4] = {1,0,-1,0};
int dp(int x,int y)
{
int &v = f[x][y]; //引用,相当于取别名
if(v != -1) return v;
v = 1;//v最差也能有自己本身一个长度的路径
for(int i = 0; i < 4; i++)//分别计算滑向四个方向
{
int a = x + dx[i], b = y + dy[i];
if(a >= 1 && a <= n && b >= 1 && b <= m && g[a][b] < g[x][y]) //a、b在边界内并且高度小于原高度才能滑下来
v = max(v,dp(a,b) + 1);//这里用的递归,分别到底计算出四个方向后,返回最大的一条路径
}
return v;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> g[i][j];
memset(f, -1,sizeof f); //初始化状态,表示没被遍历过
int res = 0;
for(int i = 1; i <= n; i++) //遍历从任意一点滑,取最大值
for(int j = 1; j <= m; j++)
res = max(res,dp(i,j));
cout << res;
return 0;
}