NYOJ 10：滑雪問題——記憶化 DFS 求最長下降路徑

問題描述

給定 R×C 高度矩陣 (R,C ≤ 100)，從任意格子出發，只能移動到上下左右相鄰且高度**嚴格更低**的格子。求最長滑雪路徑長度（格子數）。多組測試數據。

核心算法：記憶化 DFS (DP on DAG)

高度嚴格遞減 ⇒ 無環有向圖。dp[x][y] 表示從 (x,y) 出發的最長路徑長度。遞歸：

dp[x][y] = 1 + max( dp[nx][ny] ) 對所有合法鄰居 (nx,ny) 滿足 h[nx][ny] < h[x][y]

用 state[x][y] 記錄已計算值（-1 表示未計算），避免重複計算。

代碼實現

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAXN = 105;
int h[MAXN][MAXN], dp[MAXN][MAXN];
int R, C;
int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};

int dfs(int x, int y) {
    if (dp[x][y] != -1) return dp[x][y];
    int best = 0;
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx>=1 && nx<=R && ny>=1 && ny<=C && h[nx][ny] < h[x][y])
            best = max(best, dfs(nx, ny));
    }
    return dp[x][y] = best + 1;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &R, &C);
        for (int i = 1; i <= R; i++)
            for (int j = 1; j <= C; j++)
                scanf("%d", &h[i][j]);
        memset(dp, -1, sizeof(dp));
        int ans = 0;
        for (int i = 1; i <= R; i++)
            for (int j = 1; j <= C; j++)
                ans = max(ans, dfs(i, j));
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點

• 嚴格遞減保證 DAG，記憶化 DFS 時間 O(R·C)，每個狀態算一次。
• 遞歸深度最長 R·C=10000，可能棧溢出？實際測試通過，或改用拓撲序 DP（按高度降序處理）。
• 初始 dp 設 -1，區別於合法值 0（但最小路徑長度為 1，故 -1 安全）。
• 四方向擴展，邊界檢查。

拓撲序 DP 替代方案（無遞歸風險）

// 將所有格子按高度降序排序
vector> cells; // (h, x, y)
for (...) cells.push_back({h[x][y], x, y});
sort(cells.rbegin(), cells.rend()); // 降序
for (auto [hv, x, y] : cells) {
    dp[x][y] = 1;
    for (d=0..3) if (鄰居高度 < hv) dp[x][y] = max(dp[x][y], dp[nx][ny] + 1);
    ans = max(ans, dp[x][y]);
}