Python3二维列表最大价值路径求解技术求助

Hey there, let's work through your problem step by step. First, let's recap what you're trying to do: find the maximum value path from the center of a 2D grid to any of the four corners, with rules that you can only move up/down/left/right, can't revisit cells (since "can't回头" means no backtracking to already walked cells), and each cell contributes its value to the total.

What's Wrong with Your Current Code? #

Let's break down the issues causing the oversized return values and broken execution:

• Greedy Logic Doesn't Work: Your code picks the higher-value adjacent cell immediately (e.g., comparing x-1,y and x,y-1) and returns that path. But greedy choices don't guarantee the global maximum—sometimes a lower-value cell now leads to a much higher total later.
• Array Index Out-of-Bounds: Look at this line:

  return v + LT(building, x, y-1, v + building.rooms[x - 1][y].food)
  

  When x-1 >=0 is false, you're still trying to access x-1 which is negative—this will throw an error or pull garbage values, leading to incorrect totals.
• No Visited Cell Tracking: You're not marking cells as visited (like the example does with x), so your code can loop back over the same cells infinitely, causing stack overflow or exponentially growing totals.
• Limited Target: Your code only targets the top-left corner (0,0), but you need to consider all four corners as valid end points.

Fixed Approach & Code #

Here's a revised solution that addresses all these issues. We'll:

1. Track visited cells by temporarily marking them as inaccessible during recursion
2. Explore all valid, unvisited directions (up/down/left/right)
3. Return the maximum value from all possible paths to any corner
4. Handle boundary checks correctly

def max_path_to_corner(building, x, y, current_value):
    # Get grid dimensions
    rows = len(building.rooms)
    cols = len(building.rooms[0]) if rows > 0 else 0
    
    # Check if current position is a corner (end condition)
    if (x == 0 and y == 0) or (x == 0 and y == cols-1) or (x == rows-1 and y == 0) or (x == rows-1 and y == cols-1):
        return current_value + building.rooms[x][y].food
    
    # Save current cell's food value and mark as visited (using 'x' like your example)
    current_food = building.rooms[x][y].food
    building.rooms[x][y].food = 'x'  # Mark as visited
    
    max_total = -float('inf')
    # Explore all four directions
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    for dx, dy in directions:
        new_x = x + dx
        new_y = y + dy
        # Check if new position is within grid bounds and not visited
        if 0 <= new_x < rows and 0 <= new_y < cols and building.rooms[new_x][new_y].food != 'x':
            path_total = max_path_to_corner(building, new_x, new_y, current_value + current_food)
            if path_total > max_total:
                max_total = path_total
    
    # Restore the cell's value (backtracking)
    building.rooms[x][y].food = current_food
    
    # If no valid paths (dead end), return invalid value
    return max_total if max_total != -float('inf') else -float('inf')

How to Use This #

1. Find the center of your grid: for a 5x5 grid, the center is (2,2) (since indices start at 0)
2. Call the function with the starting position and initial value of 0:

   # Assuming your building is initialized with the example grid
   start_x, start_y = 2, 2
   max_value = max_path_to_corner(building, start_x, start_y, 0)
   print("Maximum path value:", max_value)
   

Key Notes #

• Backtracking: We mark cells as visited during recursion, then restore them after exploring all paths from that cell—this ensures each path only uses unique cells.
• Global Maximum: Instead of returning the first path we find, we compare all valid paths and keep the highest total.
• Corner Check: The function stops and returns the total as soon as it reaches any of the four corners.

If your grid is very large (like 100x100), recursion might hit stack limits—for those cases, you'd want to switch to an iterative approach using a stack or dynamic programming. But for smaller grids like your 5x5 example, this recursive solution works perfectly.

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