題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P1434 [SHOI2002] 滑雪

Problem Statement

題目簡述

給定一個 $R \times C$ 的矩陣，每個格子代表該位置的高度。你可以從任意一個格子出發，每次只能向上下左右四個方向中高度嚴格小於當前格子的相鄰格子移動。
求最長的移動路徑長度（包含起點）。

Constraints

約束條件

$1 \le R, C \le 100$
高度為不大於 $10000$ 的正整數。

思路：記憶化搜索

這是一個經典的網格圖上的最長路徑問題。

核心觀察

由於題目限制只能往「高度嚴格較低」的相鄰格子移動，這保證了移動路徑中絕對不會出現環。因此，整個網格可以視為一個有向無環圖 (DAG)，問題轉化為求 DAG 上的最長路徑。

狀態定義與轉移

我們可以定義一個狀態來表示「從某個特定位置出發，所能走出的最長路徑長度」。

對於任意一個位置，它的最長路徑長度取決於它周圍四個方向的相鄰位置：

檢查上下左右四個相鄰位置。
如果相鄰位置的高度嚴格小於當前位置，則可以走到該位置。
當前位置的最長路徑長度，就是所有合法相鄰位置的最長路徑長度中的最大值，再加上 1（代表當前這一步）。
如果四周都沒有更低的位置，則最長路徑長度為 1（只能停留在原地）。

避免重複計算

如果我們直接使用深度優先搜尋 (DFS) 來實作上述邏輯，會發現同一個位置可能會被多條不同的路徑重複造訪，導致大量的重複計算，時間複雜度會呈現指數級增長而超時。

記憶化搜索

為了優化，我們可以使用記憶化搜索。在第一次計算出某個位置的最長路徑長度後，將其結果儲存起來。之後如果再次造訪同一個位置，就直接回傳已儲存的結果，不再重複展開搜尋。

在 Python 中，可以直接利用 @cache 裝飾器來輕鬆達成記憶化的效果。

最終的答案即為「從網格中每一個位置出發的最長路徑長度」的最大值。

複雜度分析

時間複雜度： $\mathcal{O}(R \times C)$ 。由於使用了記憶化，網格中的每個位置最多只會被計算一次。每次計算時只需檢查四個方向，花費常數時間。
空間複雜度： $\mathcal{O}(R \times C)$ 。主要來自於遞迴呼叫的系統堆疊深度（最壞情況下路徑長度為 $R \times C$ ），以及儲存每個位置計算結果的記憶體空間。

Code

import sys
from functools import cache

sys.setrecursionlimit(int(1e4 + 5))


def solve():
    n, m = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(n)]

    @cache
    def dfs(x, y):
        res = 0
        for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] < grid[x][y]:
                res = max(res, dfs(nx, ny))
        return res + 1

    print(max(dfs(x, y) for x in range(n) for y in range(m)))


if __name__ == "__main__":
    solve()