この問題は、2次元配列の最大下降子列を求める問題と理解できます。

解法

最も単純な方法は、直接のDFS（深度優先探索）です。問題がどこからスタートするかを指定していないため、各点をスタート点としてDFSを実行し、最大値を取得します。

本問題の正解は、メモ化検索と動的計画法（DP）の2種類があります。

メモ化検索

メモ化検索では、各点からスタートし、4つの方向（上、下、左、右）に移動します。各点の検索結果をメモ化し、再利用することで計算量を削減します。

メモ化検索が有効な理由は、同じ点に再度到達しても、以前の検索結果よりも長いパスがない場合、検索を続ける必要がないためです。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 10010
using namespace std;
int n, m;
int map_data[N][N];
int memo[N][N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int max_path = -1;

int dfs(int x, int y, int last_height) {
    if (memo[x][y] != 0) return memo[x][y];
    int current_max = 0;
    for (int i = 0; i < 4; i++) {
        int new_x = x + dx[i];
        int new_y = y + dy[i];
        if (new_x > 0 && new_x <= n && new_y > 0 && new_y <= m && map_data[new_x][new_y] < last_height) {
            current_max = max(current_max, dfs(new_x, new_y, map_data[new_x][new_y]));
        }
    }
    memo[x][y] = current_max + 1;
    max_path = max(max_path, memo[x][y]);
    return memo[x][y];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &map_data[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dfs(i, j, map_data[i][j]);
        }
    }
    cout << max_path << endl;
    return 0;
}

動的計画法

動的計画法（DP）を用いる場合、状態遷移方程式は次のように定義できます：

dp[i][j] = max(dp[i][j], dp[a][b] + 1)

ただし、dp[i][j]は点(i,j)を終点としたスキーの最長パスの長さを表します。

DPを行う際には、高地から低地への移動を保証する必要があります。そのため、高度を昇順でソートし、低地から高地へと遷移します。

2次元配列を1次元に変換する方法として、行番号iと列番号jを次のように計算します：

1次元インデックス = i * m + j

#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 1010
using namespace std;

struct Point {
    int i, j, height;
};

Point points[N*N];
int dp[N][N];
int map_data[N][N];
int n, m;
int max_length = -1;

bool compare_points(Point a, Point b) {
    return a.height < b.height;
}

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map_data[i][j]);
            dp[i][j] = 1;
            points[i*m + j].height = map_data[i][j];
            points[i*m + j].i = i;
            points[i*m + j].j = j;
        }
    }
    sort(points, points + n*m, compare_points);
    for (int i = 0; i < n*m; i++) {
        for (int j = 0; j < 4; j++) {
            int new_i = points[i].i + dx[j];
            int new_j = points[i].j + dy[j];
            if (new_i >= 0 && new_i < n && new_j >= 0 && new_j < m && map_data[new_i][new_j] < points[i].height) {
                dp[points[i].i][points[i].j] = max(dp[points[i].i][points[i].j], dp[new_i][new_j] + 1);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            max_length = max(max_length, dp[i][j]);
        }
    }
    cout << max_length << endl;
    return 0;
}