I’m working on a DFS algorithm to traverse an 8×8 matrix where I need to alternate between addition and subtraction while updating the maximum values for each cell. But it is not working as I want it to work.

This is the problem I am trying to solve:

You are given a classic chess board. Each cell has a non-negative integer. The king is located in the bottom-left cell. He can move up, right, or diagonally up and right. Two players take turns. The game ends when the king comes to the right-top cell. The player who moves gets money from the other player. The amount of money is the number in the cell, where the move was ended. You need to find the value of the game. The value of the game is the amount of money that the first player will have at the end of the game. First player tries to maximize the value, while second player tries to minimize it.

Input

Eight lines, each of them contains eight non-negative integers. Each integer is less than 1000. The number in the left-bottom cell always is 0.

Output

The value of the game.

Sample input 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

Sample output 1:

4

This is the algorithm I have come up with, I added is_first_player variable, but I don’t quite understand why subtraction doesn’t work.

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)

Result:

[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]

The algorithm should correctly alternate between addition and subtraction as it traverses the matrix, and each cell in max_sum_matrix should reflect the maximum value possible for that cell. There are multiple paths for a given cell from the start position and each path results in different sum. Among these sums, the cell should contain the max one.

How can I ensure that the alternation between addition and subtraction works correctly?
Are there any issues with my current approach, and how can I address them?