这道题本来可以用dfs做,但这样会超时,因为需要对每一个点进行dfs求从该点出发的最长距离,但我们在对一个点dfs的过程中,往往可以求到很多点,所以对每一个点dfs实际上是多余的,所以我们在dfs的基础上加上dp就可以得到答案。
#include<iostream>
#include<string.h>
#include<string>
#include<sstream>
#include<vector>
#include<deque>
#include<map>
#include<algorithm>
#include<iomanip>
#include<math.h>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int grid[105][105];
int len[105][105];
int r, c;
int dir[4][2] = { 0,1,0,-1,1,0,-1,0 };
int dp(int a,int b)
{
if (len[a][b])
return len[a][b];
int maxlen = 0;
for (int i = 0; i < 4; i++)
{
int x = a + dir[i][0];
int y = b + dir[i][1];
int ans;
if (x<1 || x>r || y<1 || y>c)
{
continue;
}
if (grid[x][y] < grid[a][b])
{
ans = dp(x, y);
maxlen = max(ans, maxlen);
}
}
len[a][b] = maxlen + 1;
return maxlen+1;
}
int main()
{
while (cin >> r >> c)
{
memset(len, 0, sizeof(len));
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
cin >> grid[i][j];
int maxlen = 0;
for (int i = 1; i <= r; i++)
{
for (int j = 1; j <= c; j++)
{
int ret = dp(i, j);
maxlen = max(ret, maxlen);
}
}
cout << maxlen << endl;
}
return 0;
}