算法:记忆化搜索
f[i][j]:以(i,j)为起点的所有路径集合
属性:max
它会由四个方向的结果产生(这四个方向的高度需要严格小于(i,j)点的高度才行)
f[i][j] = max(f[i][j],f[i - 1][j] + 1,f[i + 1][j] + 1,f[i][j - 1] + 1,f[i][j + 1] + 1)
C++ 代码
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
typedef pair<int,int> PII;
const int N = 305;
int r,c;
int g[N][N];
int f[N][N];
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
map<PII,PII> path;
int dfs(int x,int y)
{
if(f[x][y]) return f[x][y];
f[x][y] = 1;
int tmax = 1,rx = 0,ry = 0;
for(int i = 0;i < 4;i ++ )
{
int tx = x + dx[i],ty = y + dy[i];
if(tx < 1 || tx > r || ty < 1 || ty > c || g[x][y] <= g[tx][ty]) continue;
int tmp = dfs(tx,ty) + 1;
if(tmp > tmax)
{
tmax = tmp;
rx = tx,ry = ty;
}
}
f[x][y] = tmax;
path[{x,y}] = {rx,ry};
return f[x][y];
}
int main()
{
cin >> r >> c;
for(int i = 1;i <= r;i ++ )
for(int j = 1;j <= c;j ++ )
cin >> g[i][j];
int res = 0;
PII id;
for(int i = 1;i <= r;i ++ )
for(int j = 1;j <= c;j ++ )
{
dfs(i,j);
if(f[i][j] > res)
{
res = f[i][j];
id.first = i,id.second = j;
}
}
cout << res << endl;
while(id.first != 0)
{
cout << id.first << " " << id.second << endl;
id = path[id];
}
return 0;
}