如何查找二维列表的最大邻域值？从中心迭代移动至最大值位置

Alright, let's work through this problem together. You've already got the center position of your 2D list (like the value 10 in your example), so now we need to build the logic to find the maximum neighbor at each step, move there, and repeat until we hit a local peak or a loop. I'll use Python for the example since it's intuitive for list operations.

First, let's lay down the foundational functions we'll need: getting valid neighbors, finding the max neighbor position, and (for completeness) confirming the center position (since you mentioned you already have this, but it's good to include for context).

Get the Center Position #

This is the function you've already implemented, but here's a clean version:

def get_center(grid):
    rows = len(grid)
    cols = len(grid[0]) if rows > 0 else 0
    center_row = rows // 2
    center_col = cols // 2
    return (center_row, center_col)

Get Valid Neighbors #

We need to generate all neighbor positions that stay within the bounds of the 2D list. By default, this uses 8-directional neighbors (up, down, left, right, and all four diagonals). If you want 4-directional instead, just adjust the offsets list.

def get_valid_neighbors(row, col, grid):
    rows = len(grid)
    cols = len(grid[0])
    # 8-directional offsets (remove diagonals for 4-directional)
    offsets = [(-1,-1), (-1,0), (-1,1),
               (0,-1),          (0,1),
               (1,-1),  (1,0), (1,1)]
    
    valid_neighbors = []
    for dr, dc in offsets:
        new_row = row + dr
        new_col = col + dc
        # Ensure we don't go out of the grid's bounds
        if 0 <= new_row < rows and 0 <= new_col < cols:
            valid_neighbors.append((new_row, new_col))
    return valid_neighbors

Find the Maximum Neighbor Position #

This function checks all valid neighbors, finds the one with the highest value, and returns its position. If all neighbors are smaller than the current value (we've hit a local peak), it returns None to signal we should stop.

def find_max_neighbor_pos(row, col, grid):
    neighbors = get_valid_neighbors(row, col, grid)
    max_value = -float('inf')
    max_pos = None
    
    for r, c in neighbors:
        if grid[r][c] > max_value:
            max_value = grid[r][c]
            max_pos = (r, c)
    
    # Stop if current position is the local peak
    if max_value <= grid[row][col]:
        return None
    return max_pos

Now we'll create the main function that starts at the center, repeatedly moves to the max neighbor, and tracks the path. We'll also add a check to prevent infinite loops (like if two positions have equal values and keep bouncing between each other).

def iterate_from_center(grid):
    current_pos = get_center(grid)
    path = [current_pos]  # Track our movement path for debugging
    
    while True:
        next_pos = find_max_neighbor_pos(*current_pos, grid)
        
        # Stop conditions: local peak detected, or loop detected
        if next_pos is None:
            print("Reached a local peak. Stopping iteration.")
            break
        if next_pos in path:
            print("Detected a loop between positions. Stopping iteration.")
            break
        
        path.append(next_pos)
        current_pos = next_pos
    
    # Print the results in a readable format
    print("\nMovement Path (format: (row, column)):")
    for step, pos in enumerate(path, 1):
        r, c = pos
        print(f"Step {step}: Position {pos} | Value: {grid[r][c]}")
    print(f"\nFinal Position: {current_pos} | Final Value: {grid[current_pos[0]][current_pos[1]]}")
    
    return path

Let's test this with your example scenario (center value 10) and another case where the center isn't the peak.

Test 1: Center is the Local Peak #

# 3x3 grid with center value 10 (local peak)
grid = [
    [1, 3, 5],
    [7, 10, 8],
    [2, 4, 7]
]
iterate_from_center(grid)

Output:

Reached a local peak. Stopping iteration.

Movement Path (format: (row, column)):
Step 1: Position (1, 1) | Value: 10

Final Position: (1, 1) | Final Value: 10

Test 2: Center is Not the Peak #

# 3x3 grid where center can move to a higher value
grid = [
    [1, 3, 15],
    [7, 10, 8],
    [2, 4, 7]
]
iterate_from_center(grid)

Output:

Reached a local peak. Stopping iteration.

Movement Path (format: (row, column)):
Step 1: Position (1, 1) | Value: 10
Step 2: Position (0, 2) | Value: 15

Final Position: (0, 2) | Final Value: 15

• Change Neighbor Direction: Modify the offsets list in get_valid_neighbors to use only 4-directional movement (remove the diagonal offsets).
• Adjust Loop Handling: If you want to allow movement between equal-value positions, remove the if next_pos in path check (just be aware this could cause infinite loops).
• Add Iteration Limit: For large grids, you might want to add a max step count to the loop (e.g., max_steps = 100 and increment a counter each iteration).

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