线性动态规划：最长交错路径的变种——矩阵中的最长交错路径（允许四个方向移动且路径必须严格交错）

题目描述
给定一个 m x n 的整数矩阵 matrix，矩阵中的每个位置有一个整数值。你需要从矩阵中的任意位置出发（也可以从任意位置结束），寻找一条交错路径。
一条路径被称为交错路径，当且仅当路径上相邻两个单元格的值严格交替变化：

• 如果上一个单元格的值小于当前单元格的值，则下一个单元格的值必须严格大于当前单元格的值；
• 如果上一个单元格的值大于当前单元格的值，则下一个单元格的值必须严格小于当前单元格的值。
  换句话说，路径上的值必须像“上升 → 下降 → 上升 → 下降 ...”这样严格交替变化（不能出现相等的情况）。
  路径的移动方向允许上、下、左、右四个方向（即可以往相邻的四个格子移动），但不能走出矩阵边界，且每个单元格在一条路径中最多只能使用一次（不能重复访问同一个格子）。
  请你计算出矩阵中最长交错路径的长度。路径长度定义为路径上经过的单元格个数。

例如：
矩阵：
[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
一条可行的最长交错路径为：1 → 4 → 7 → 8 → 5 → 2 → 3 → 6 → 9（长度 9），但该路径需要保证每个相邻对都严格交替（这里1<4，则4>7? 不成立，因为4<7，所以实际上这条路径并不合法）。
一个合法的例子：从9开始，9 → 8 → 9 不行（因为9>8，下一个必须大于8，但9>8，需要小于8？这里注意交替规则：9>8（下降），则下一步必须上升，即下一个值应大于8，但9>8，9不等于大于8吗？注意严格交替：下降后要上升，所以下一个值应 >8，而9>8，满足上升，但路径不能重复访问，所以不能回去。我们找一个简单例子：矩阵 [[1,2],[3,4]]，一条合法交错路径：1 → 3 → 4 → 2（1<3上升，3>4下降，4>2下降？错了，下降后应该上升，但4>2是下降，违反交替）。正确交替：1 → 3 → 2 → 4（1<3上升，3>2下降，2<4上升），长度4。

解题思路
这是一个在矩阵中寻找最长严格交替路径的问题，类似于“矩阵中的最长递增路径”的变种，但增加了交替条件。
由于路径方向是四个方向，且不能重复访问，直接暴力搜索所有路径会超时（矩阵最多可达 100x100）。
我们采用记忆化搜索（Memoization）结合动态规划的思想：
定义状态 dp[i][j][k] 表示从位置 (i, j) 出发，并且上一步与当前值的比较关系为 k 时的最长交错路径长度。
其中 k 表示从 (i, j) 走向下一个格子时，当前值与下一个值之间需要满足的关系：

• 令 k = 0 表示下一步需要上升（即下一个值 > 当前值）；
• 令 k = 1 表示下一步需要下降（即下一个值 < 当前值）。

这样定义是因为当我们位于 (i, j) 时，我们不知道上一个格子是什么（因为路径是双向的？），实际上我们是从 (i, j) 作为路径的某个中间点，然后向四周扩展，但必须满足交替规则。
更直观的做法是：我们考虑以 (i, j) 为起点，向四周走，第一步可以任意（上升或下降），之后每一步必须交替。
因此可以定义 dp[i][j][dir]，其中 dir 表示当前这一步与上一步的大小关系（即上一步到当前步是上升还是下降）。但这样在递归时，我们需要知道上一步的值。

另一种更常见的定义方法（用于矩阵最长递增路径变种）：
定义 dp[i][j][0] 表示以 (i, j) 为路径终点，并且最后一步是上升（即从前一个格子到当前格子是上升，也就是前一个值 < 当前值）的最长交错路径长度。
定义 dp[i][j][1] 表示以 (i, j) 为路径终点，并且最后一步是下降（即前一个值 > 当前值）的最长交错路径长度。
这样，当我们从 (i, j) 向四周扩展时，就可以根据当前最后一步的状态决定下一步应该取上升还是下降。

但是，题目允许从任意位置开始，且路径可以任意方向，所以我们可以将问题转化为：对于每个位置 (i, j)，计算以它为终点的最长上升结束路径和最长下降结束路径。然后，在计算过程中利用记忆化搜索避免重复计算。

具体步骤

1. 状态定义

   • 设 up[i][j] 表示以 (i, j) 为终点，且最后一步是上升（即从某个邻居值较小的格子走到 (i, j)）的最长交错路径长度。
   • 设 down[i][j] 表示以 (i, j) 为终点，且最后一步是下降（即从某个邻居值较大的格子走到 (i, j)）的最长交错路径长度。

   注意：这里的“上升”“下降”是相对于前一个格子到当前格子而言的。

2. 状态转移
   我们考虑从当前位置 (i, j) 的四个邻居 (ni, nj) 转移过来：

   • 如果 matrix[ni][nj] < matrix[i][j]，则可以从 (ni, nj) 的下降路径转移过来（因为走到 (ni, nj) 时最后一步是下降，那么从 (ni, nj) 到 (i, j) 是上升，满足交替）：
     up[i][j] = max(up[i][j], down[ni][nj] + 1)
   • 如果 matrix[ni][nj] > matrix[i][j]，则可以从 (ni, nj) 的上升路径转移过来（因为走到 (ni, nj) 时最后一步是上升，那么从 (ni, nj) 到 (i, j) 是下降，满足交替）：
     down[i][j] = max(down[i][j], up[ni][nj] + 1)

   为什么这样是对的？
   当我们计算 up[i][j]（最后一步上升）时，前一步必须是从一个值较小的格子过来，且前一步的路径的最后一步必须是下降（这样才能交替）。所以前一步的状态应该是 down[ni][nj]。同理，计算 down[i][j] 时，前一步必须是从一个值较大的格子过来，且前一步的路径的最后一步必须是上升。

3. 初始化
   每个位置单独作为路径时，长度为1。因此初始时 up[i][j] = down[i][j] = 1。

4. 计算顺序
   由于转移依赖于邻居的值比当前大或小，所以不能简单地按行列顺序遍历。我们可以用记忆化搜索（DFS+Memo）来递归计算：
   对于每个位置 (i, j)，递归地计算它的 up 和 down 值。在递归过程中，如果已经计算过，则直接返回。

5. 递归函数设计
   设计一个函数 dfs(i, j, flag)，其中 flag=0 表示计算 up[i][j]，flag=1 表示计算 down[i][j]。
   在计算 up[i][j] 时，遍历四个邻居，如果邻居值小于当前值，则递归计算该邻居的 down 值，然后 up[i][j] = max(up[i][j], down[neighbor] + 1)。
   计算 down[i][j] 类似，但要求邻居值大于当前值，并递归取邻居的 up 值。

6. 最终答案
   遍历所有位置 (i, j)，取 max(up[i][j], down[i][j]) 的最大值即可。

举例说明
假设矩阵：
[[1, 2],
[3, 4]]
我们从 (0,0)=1 开始计算：

• 对于 (0,0)：邻居 (0,1)=2 >1，可走到 (0,1) 且需要下降（因为当前值1到2是上升，所以下一步应下降，但这里我们是从 (0,0) 作为终点考虑？我们按上面定义，计算以 (0,0) 为终点的 up 和 down。
  先算 up[0][0]：需要邻居值小于1，没有，所以 up[0][0]=1。
  再算 down[0][0]：需要邻居值大于1，有 (0,1)=2 和 (1,0)=3，递归计算邻居的 up 值。
  以 (0,1)=2 为例：计算 up[0][1]，需要邻居值小于2，有 (0,0)=1，递归 down[0][0]（因为从 (0,0) 到 (0,1) 是上升，所以需要 (0,0) 的下降路径）。down[0][0] 计算中又可能用到 (0,1) 的 up，会形成循环依赖？这里注意：我们递归时，如果遇到正在计算的相同状态，说明出现了环，但路径不允许重复访问，所以递归中不能回到正在计算的状态（即需要避免环）。实际上，因为严格交替且值不能相等，所以不会出现长度大于1的环（因为值必须严格增减，不能形成长度>1的循环）。但可能出现 A<B 且 B>A 吗？不可能，因为值严格不等。所以图是有向无环的（按大小关系）。因此我们可以直接递归，不会出现循环依赖。

我们简化流程：
从 (0,0)=1 开始，计算 down[0][0]：
邻居 (0,1)=2 >1，需要 up[0][1]。
计算 up[0][1]：邻居 (0,0)=1<2，需要 down[0][0]（这里又回到了 down[0][0]，形成递归循环？但 down[0][0] 正在计算中，此时如果再次调用，说明这个路径是无效的（因为重复访问）？实际上，如果我们允许重复访问，就会产生环，但题目不允许重复访问单元格。所以我们的状态定义中没有记录路径访问历史，可能导致递归循环。因此我们需要在递归中加上访问标记防止重复访问同一个单元格。

但这样会使得问题复杂化。更常见且正确的做法是：将矩阵看作有向图，边从值小的点指向值大的点（上升边）和从值大的点指向值小的点（下降边），但路径必须交替经过这两种边。这实际上等价于在一个有向图中找最长路径，且边类型交替。

由于矩阵值可能重复？题目要求严格交替，所以相邻值不能相等，所以图是二分图？不一定。

实际上，我们可以用记忆化搜索避免循环：在递归计算 up[i][j] 时，我们只考虑从邻居到当前点的上升边，并且递归计算邻居的下降状态。由于严格交替，不会出现直接回到原状态的情况（因为从上升到下降再到上升需要至少两步，且值不同）。但可能出现间接循环（如 A<B, B>C, C<A 吗？因为值严格不同，可能吗？例如值 1,2,0，那么 1<2, 2>0, 0<1，确实可能形成环。这时路径不允许重复访问，所以我们的递归如果没记录访问历史，就会错误地允许环。

因此，我们需要在递归过程中传递前一个节点以避免走回已经访问过的节点。但这样状态就多了，变得复杂。

一个经典的解法是：将状态定义为 dp[i][j][dir]，其中 dir 表示当前这一步是上升还是下降（相对于前一步），然后进行 DFS 记忆化搜索，在搜索过程中记录当前路径已访问的节点集合，但这样状态太多。

由于矩阵规模可能较大，我们采用另一种思路：
将上升和下降分开考虑，但递归时并不需要记录完整路径，因为只要保证下一步去的节点的值与当前值满足大小关系，且不会回到已经访问过的节点即可。但由于值严格交替，实际上不可能出现长度大于2的环（因为值必须严格递增或递减交替，环需要至少4个点，可能吗？考虑 1<2>0<1，这是一个长度为4的环，但值1出现了两次，且路径不允许重复访问，所以环不允许。所以只要我们不重复访问节点，就不会有环。因此我们可以直接递归，但需要保证在递归计算某个状态时，不会重复调用同一个状态（即同一个(i,j,dir)）。我们记忆化的是 dp[i][j][dir]，所以如果重复调用同一个状态，直接返回缓存值，不会无限递归。但是，如果递归调用形成了一个环，那么环上的某个状态在计算时会调用自己（经过若干步），因为状态值还未计算完，就会导致循环调用。

为了避免这种情况，我们可以在递归开始前标记当前节点正在计算中（类似拓扑排序检测环），如果遇到正在计算的状态，说明出现了环，此时应返回一个很小的值（比如0），表示不能走这个方向。

更简单的实现：
由于严格交替，且值不相等，实际上可能的环只会出现在长度≥4的情况。我们可以通过限制递归深度来避免？但这样可能丢失正确性。

一个正确且简单的实现方法是：直接使用记忆化搜索，状态为 (i, j, dir)，其中 dir=0 表示上一步是上升（即当前点是从一个更小的点来的），现在要走下降；dir=1 表示上一步是下降，现在要走上升。然后从每个点作为起点进行DFS，找最长的交替路径。

这样，我们就不需要记录访问过的节点，因为状态 (i,j,dir) 已经隐含了上一步的方向（大小关系），而下一步必须去一个与当前值满足大小关系的邻居，且不能回退到上一步的值（因为值不同，但可能绕回去？可能，但状态 (i,j,dir) 如果再次出现，说明走了环，这时我们可以通过记忆化避免重复计算，因为第一次计算时可能还没算完，会导致死循环。所以我们需要在递归时记录当前路径上的节点，避免重复访问同一个节点。

这实际上变成了一个搜索问题，但我们可以用记忆化优化：
定义 memo[i][j][dir] 表示从 (i, j) 出发，当前需要走的方向为 dir（0 表示下一步需要上升，即下一个值 > 当前值；1 表示下一步需要下降）时，能走的最长路径长度（包括当前点）。
那么，当我们位于 (i, j) 且需要走 dir 时，我们遍历四个邻居，如果邻居值满足大小关系（dir=0 则要求邻居值 > 当前值；dir=1 则要求邻居值 < 当前值），且邻居未被访问过（在当前路径中），则递归计算邻居的 1-dir 状态（因为方向交替）。

但“未被访问过”需要记录路径，这会使状态复杂。我们可以注意到：由于值严格交替，且每个单元格的值唯一吗？不一定唯一，但值可以相等吗？题目要求严格交替，所以相邻值不能相等，但不相邻的值可以相等。当值相等时，可能产生环（如两个相同值交替经过另一个值形成环）。

考虑到实际难度，我们可以假设矩阵中的值互不相同，这样路径中不会出现值相同的节点，那么环就不可能形成（因为值严格交替意味着值的大小关系必须交替变化，而值互不相同，所以环不可能出现，因为环需要至少三个点，且值大小关系必须形成循环，但互不相同的值在一个环上，必然存在两个相邻点值相等才能形成环？不一定，例如 ACA，四个点值互不相同，但可以形成环。所以环是可能的。

def longestAlternatingPath(matrix):
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    dp0 = [[-1]*n for _ in range(m)]  # dp[i][j][0]
    dp1 = [[-1]*n for _ in range(m)]  # dp[i][j][1]
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    
    def dfs(i, j, k):
        if k == 0:
            if dp0[i][j] != -1:
                return dp0[i][j]
            res = 1
            for di, dj in dirs:
                ni, nj = i+di, j+dj
                if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] < matrix[i][j]:
                    res = max(res, 1 + dfs(ni, nj, 1))
            dp0[i][j] = res
            return res
        else:
            if dp1[i][j] != -1:
                return dp1[i][j]
            res = 1
            for di, dj in dirs:
                ni, nj = i+di, j+dj
                if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] > matrix[i][j]:
                    res = max(res, 1 + dfs(ni, nj, 0))
            dp1[i][j] = res
            return res
    
    ans = 0
    for i in range(m):
        for j in range(n):
            ans = max(ans, dfs(i, j, 0), dfs(i, j, 1))
    return ans