如何确保矩阵DFS遍历中加减操作交替正确？问题排查与修正

当前代码的核心问题 #

• 访问标记逻辑错误：visited集合会阻止同一单元格被不同路径访问，但博弈场景中，同一单元格可能由先手或后手到达，这是两种完全不同的状态，需要分别计算收益，不能用坐标直接标记已访问。
• 状态存储缺失：max_sum_matrix仅存储单一最大值，未区分到达该单元格的玩家身份（先手/后手），导致无法实现"先手最大化收益、后手最小化收益"的博弈逻辑。
• 收益计算时机错误：起点(7,0)的0值不应该被计入收益（规则是移动到目标单元格时获得该值），当前代码在进入起点时就执行了加法，虽然数值无影响，但逻辑不符合规则。

修正后的实现方案 #

核心思路 #

使用记忆化搜索，维护两个二维数组：

• memo_max[x][y]：先手到达(x,y)时，能获得的最大收益
• memo_min[x][y]：后手到达(x,y)时，能让先手获得的最小收益（因为后手会选择对自己最有利的路径，即最小化先手收益）

递归逻辑：

1. 若已到达右上角(0,7)，返回当前收益
2. 若当前是先手，遍历所有可行移动，选择能让收益最大化的路径（对每个下一步，调用后手状态的递归，取最大值）
3. 若当前是后手，遍历所有可行移动，选择能让收益最小化的路径（对每个下一步，调用先手状态的递归，取最小值）
4. 用记忆化缓存已计算的状态，避免重复递归

修正代码 #

import sys

def calculate_game_value(matrix):
    n = len(matrix)
    # 记忆化数组：memo_max[x][y]是先手到达(x,y)的最大收益，memo_min是后手到达的最小收益
    memo_max = [[-sys.maxsize] * n for _ in range(n)]
    memo_min = [[sys.maxsize] * n for _ in range(n)]
    directions = [(0, 1), (-1, 1), (-1, 0)]  # 右、右上、上

    def is_valid(x, y):
        return 0 <= x < n and 0 <= y < n

    def dfs(x, y, is_first_player):
        # 终止条件：到达右上角
        if x == 0 and y == n-1:
            return 0
        
        # 记忆化查询，避免重复计算
        if is_first_player:
            if memo_max[x][y] != -sys.maxsize:
                return memo_max[x][y]
        else:
            if memo_min[x][y] != sys.maxsize:
                return memo_min[x][y]
        
        best_value = -sys.maxsize if is_first_player else sys.maxsize
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if is_valid(nx, ny):
                # 移动到(nx, ny)，获取该单元格的值
                cell_value = matrix[nx][ny]
                # 递归计算下一步的收益
                next_value = dfs(nx, ny, not is_first_player)
                # 根据玩家身份更新当前最优值
                if is_first_player:
                    # 先手要最大化：当前收益 = 单元格值 + 下一步后手带来的收益
                    current = cell_value + next_value
                    if current > best_value:
                        best_value = current
                else:
                    # 后手要最小化：当前收益 = -单元格值 + 下一步先手带来的收益（因为后手获得该值，相当于先手损失）
                    current = -cell_value + next_value
                    if current < best_value:
                        best_value = current
        
        # 缓存结果
        if is_first_player:
            memo_max[x][y] = best_value
        else:
            memo_min[x][y] = best_value
        
        return best_value
    
    # 起点是(7,0)，先手开始，初始收益为0（还未移动）
    return dfs(7, 0, True)

# 示例输入1（注意输入的行顺序：原示例输入是从第一行到第八行，对应矩阵的x从0到7）
sample_matrix = [
    [0, 1, 0, 1, 0, 1, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0, 1, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0, 1, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0, 1, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0]
]

# 计算并输出结果
print(calculate_game_value(sample_matrix))  # 输出：4

代码说明 #

• 记忆化缓存：memo_max和memo_min分别存储两种玩家状态下的最优收益，避免重复递归计算同一状态。
• 博弈逻辑实现：先手选择能最大化自己收益的路径，后手选择能最小化先手收益的路径，完全符合问题描述的规则。
• 收益计算：移动到目标单元格时才计算该单元格的价值，先手获得则加，后手获得则减（相当于先手的收益减少）。

内容的提问来源于stack exchange，提问作者Muzaffer Eyvazov