题目不让复制,这是题目大意:
有一个n行m列的矩阵,每一个数都是正整数,从矩阵的任何一个点出发,每次可以到这个位置相邻四个位置中比这个点的值小的位置,问最长路径的长度
1 <= n, m <= 100
矩阵中的每一个数不超过1000
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, a[105][105], mem[105][105], maxx;
int dfs(int r, int c)
{
if (mem[r][c]) return mem[r][c];
int res = 1;
if (r > 1 && a[r][c] > a[r - 1][c]) res = max(res, dfs(r - 1, c) + 1);
if (r < n && a[r][c] > a[r + 1][c]) res = max(res, dfs(r + 1, c) + 1);
if (c > 1 && a[r][c] > a[r][c - 1]) res = max(res, dfs(r, c - 1) + 1);
if (c < n && a[r][c] > a[r][c + 1]) res = max(res, dfs(r, c + 1) + 1);
return mem[r][c] = res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
maxx = max(maxx, dfs(i, j));
cout << maxx;
return 0;
}
WA了一个测试点。