R001 记忆化搜索 ABCPATH - SPOJ 有方向的搜索

例题：

• ABCPATH - SPOJ

题意：

给你一个二维字母网格图，求从字母 A 开始的最长连续字母路径长度，枚举方向包括水平、垂直和对角线。

特点：

1. DFS参数：从根节点向周围扩散，取子节点返回的最大值作为当前的返回值。
2. 搜索条件：有明显的方向，比如这里 A -> B -> C -> D ··· ，可以不使用 vised 数组。可以理解为网格图上进行拓扑排序求最长路。
3. 关键优化：存在重叠子问题需要记忆化。

具体代码为

memo = [[0] * m for _ in range(n)]  # 记忆化数组，标记这个位置已经更新
def dfs(i, j):
    if memo[i][j] != 0:
        return memo[i][j]
    res = 1
    for dx, dy in dirr:
        a, b = i + dx, j + dy
        if 0 <= a < n and 0 <= b < m:
            if ord(g[a][b]) == ord(g[i][j]) + 1:  # 保持有方向的搜索
                res = Max(res, 1 + dfs(a, b))  # 对子节点的贡献取max
    memo[i][j] = res
    return res

类似题目：

• Longest Path - CodeChef
  • 这道题目数据较弱不需要记忆化也可以通过。
• P1101 单词方阵 - 洛谷
  • 可以使用搜索，也可以直接枚举八个方向再 while 循环判断。