DFS矩阵遍历时如何保证加减法正确交替？

Question

我正在研究一种 DFS 算法来遍历 8x8 矩阵，其中我需要在加法和减法之间交替，同时更新每个单元格的最大值。但它没有像我希望的那样工作。

这就是我要解决的问题：

您将获得一个经典的棋盘。每个单元格都有一个非负整数。国王位于左下角的单元格中。他可以向上、向右或对角向上、向右移动。两名玩家轮流进行。当国王来到右上角的格子时游戏结束。移动的玩家从其他玩家那里获得金钱。金额是移动结束的单元格中的数字。你需要找到游戏的价值。游戏的价值是第一个玩家在游戏结束时将拥有的金钱数量。第一个玩家尝试最大化价值，而第二个玩家尝试最小化价值。

输入

八行，每行包含八个非负整数。每个整数都小于 1000。左下单元格中的数字始终为 0。

输出

游戏的价值。

示例输入1：

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

输出示例1：

4

这是我想出的算法，我添加了

is_first_player

变量，但我不太明白为什么减法不起作用。

def dfs_matrix_max_sum(matrix):
    n = len(matrix)
    max_sum_matrix = [[-sys.maxsize] * n for _ in range(n)]  
    visited = set()
    
    def is_valid(x, y):
        return 0 <= x < n and 0 <= y < n
    
    def dfs(x, y, current_sum, is_first_player):
        if not is_valid(x, y) or (x, y) in visited:
            return
        
        visited.add((x, y))
        
        if is_first_player:
            current_sum += matrix[x][y]  # First player adds
        else:
            current_sum -= matrix[x][y]  # Second player subtracts
        
        # Update the cell with the maximum sum encountered so far
        if current_sum > max_sum_matrix[x][y]:
            max_sum_matrix[x][y] = current_sum
            
            # Define directions: right, diagonally upright, up
            directions = [(0, 1), (-1, 1), (-1, 0)]
            
            for dx, dy in directions:
                new_x, new_y = x + dx, y + dy
                dfs(new_x, new_y, current_sum, not is_first_player)
        
        visited.remove((x, y))
    
    dfs(7, 0, 0, True)
    
    return max_sum_matrix

matrix = [
    [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, 0],
    [0, 0, 1, 0, 1, 0, 1, 0]
]

result = dfs_matrix_max_sum(matrix)

for row in result:
    print(row)

结果：

[3, 3, 4, 4, 5, 5, 6, 6]
[3, 3, 4, 4, 5, 5, 6, 6]
[2, 2, 3, 3, 4, 4, 5, 5]
[2, 2, 3, 3, 4, 4, 5, 5]
[1, 1, 2, 2, 3, 3, 4, 4]
[1, 1, 2, 2, 3, 3, 4, 4]
[0, 0, 1, 1, 2, 2, 3, 3]
[0, 0, 1, 1, 2, 2, 3, 3]

算法在遍历矩阵时应正确地在加法和减法之间交替，并且

 max_sum_matrix

中的每个单元格应反映该单元格可能的最大值。对于给定单元格，从起始位置开始有多个路径，并且每个路径产生不同的总和。在这些总和中，单元格应包含最大的一个。

如何保证加减法的交替正确进行？ 我当前的方法是否存在任何问题？我该如何解决这些问题？

Answer 1

问题是你总是最大化一个单元格的结果，而对手会尽一切努力最小化它。因此，如果对手发现减少它的动作，您也应该跟踪它，因为它是最大化玩家下一步动作的起点。

这意味着您需要跟踪每个单元格的两个分数，具体取决于谁最后到达该单元格。下一位玩家应该从对手的角度在（所考虑的走法）起始单元取得最佳分数，然后力争在三个可能的走法中获得最佳结果。

还要注意，DFS 对于此类问题并不是那么有效：它将继续寻找路径，可能直到最后，即使后来发现在该路径的中途，有一条更优的路线可以到达到该单元格 - 使该点之后已经完成的所有工作无效。

逐行增量方法（动态规划，类似于 BFS 方法）更适合这个问题。

这是一个可能的实现：

def matrix_max_sum(matrix):
    prev_row = []
    for row in reversed(matrix):
        curr_row = []
        for c, money in enumerate(row):
            if c:  # Not left-most column
                if prev_row:  # Not left-most column & not bottom row
                    mini, maxi = (  # Three possible moves: take best (for both players)
                        max(prev_row[c][0], prev_row[c-1][0], curr_row[-1][0]),
                        min(prev_row[c][1], prev_row[c-1][1], curr_row[-1][1])
                    )
                else:  # Not left-most column, but bottom row
                    mini, maxi = curr_row[-1]
            elif prev_row:  # Left-most column, but not bottom row
                mini, maxi = prev_row[c]
            else:  # Bottom-left corner cell
                mini, maxi = 0, 0
            # Add the money to the best source cell, from viewpoint of opponent
            curr_row.append((money + maxi, money + mini))
        prev_row = curr_row

    # We have a score for when player 1 or 2 makes last move: get best of both
    return max(prev_row[-1])