网格内同名点无交叉路径连接算法故障排查求助

问题背景 #

输入包含高度、宽度及带名称点的网格图，需判断所有同名点能否在路径不交叉的情况下两两连接。当前Python实现中，所有本该返回possible的输入均返回impossible，需排查修复。

现有代码 #

# Function to read input from a file and process it
def is_possible_to_connect(h, w, named_vertices):
    # Create a grid to represent the graph.
    graph = [[None for _ in range(w)] for _ in range(h)]

    # Initialize the graph with named vertices
    for (row, col, name) in named_vertices:
        if 0 <= row < h and 0 <= col < w:
            if graph[row][col] is None:
                graph[row][col] = name
            else:
                return "impossible"  # Two named vertices with the same coordinates
        else:
            return "impossible"  # Named vertex coordinates out of bounds

    # Define the four possible directions (up, down, left, right)
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def is_valid_move(row, col):
        return 0 <= row < h and 0 <= col < w

    def dfs(row, col, prev_name):
        if not is_valid_move(row, col):
            return True  # Reached outside the grid

        # Check if we encounter a named vertex or a path
        current_vertex = graph[row][col]
        if current_vertex is not None:
            if current_vertex != prev_name:
                return False  # Encountered a different named vertex
            else:
                return True  # Reached the same named vertex again

        graph[row][col] = prev_name  # Mark the current cell as visited

        # Recursively explore all four directions
        for dr, dc in directions:
            if not dfs(row + dr, col + dc, prev_name):
                return False

        return True

    # Check if it's possible to connect the named vertices without crossing
    for row in range(h):
        for col in range(w):
            if graph[row][col] is not None:
                if not dfs(row, col, graph[row][col]):
                    return "impossible"

    return "possible"


data = [
    (2, 3, [(0, 1, 'A'), (0, 2, 'B'), (2, 1, 'C'), (2, 0, 'D')]), #impossible
    (2, 3, [(1, 0, 'A'), (2, 1, 'A')]), #possible
    (2, 3, [(1, 3, 'A'), (0, 0, 'B'), (0, 1, 'A'), (2, 0, 'B')]), #possible
    (2, 3, [(2, 3, 'A'), (1, 0, 'A'), (0, 1, 'B'), (2, 2, 'B')]) #impossible
]

for row in data:
    h, w, name = row
    result = is_possible_to_connect(h, w, named_vertices)
    print(result)

预期与实际输出 #

• 预期输出：

  impossible
  possible
  possible
  impossible
  

• 实际输出：

  impossible
  impossible
  impossible
  impossible
  

错误原因分析 #

1. 变量解包与传参错误
   测试循环中，解包row为h, w, name，但调用函数时使用未定义的named_vertices，导致所有测试用例实际传入错误参数，直接触发边界判断返回impossible。

2. 坐标范围不匹配
   测试用例中部分点的坐标超出网格范围（如第二个测试用例的(2,1,'A')，h=2时行索引仅能取0、1），初始化阶段直接返回impossible。

3. DFS逻辑偏离需求
   当前DFS从命名点出发，将所有可达空白格标记为当前名称，且只要任一方向返回False就终止。该逻辑既未实现配对连接同名点，也未处理路径不交叉的约束，反而会占用所有空白格，导致后续点无法处理。

4. 未校验同名点数量
   未提前统计每个名称的出现次数，若存在奇数次的名称，本身就无法两两配对，需直接返回impossible。

修复方案 #

核心修改点 #

• 修正测试循环的变量解包与传参
• 统一坐标为0-based（或调整网格边界判断适配1-based输入）
• 新增同名点数量校验，非偶数直接返回impossible
• 重构DFS为配对连接逻辑：针对每对未连接的同名点，用DFS寻找路径，标记临时占用，找到后保留路径避免交叉，失败则回溯

修复后代码 #

from collections import defaultdict

def is_possible_to_connect(h, w, named_vertices):
    # 统计每个名字的点，检查数量是否为偶数
    name_points = defaultdict(list)
    for row, col, name in named_vertices:
        # 输入坐标按1-based处理，转为0-based
        row_idx = row - 1
        col_idx = col - 1
        if not (0 <= row_idx < h and 0 <= col_idx < w):
            return "impossible"
        name_points[name].append((row_idx, col_idx))
    
    for name, points in name_points.items():
        if len(points) % 2 != 0:
            return "impossible"
    
    # 初始化网格：None为空白，命名点保留名称，'used'为已占用路径
    grid = [[None for _ in range(w)] for _ in range(h)]
    for name, points in name_points.items():
        for row, col in points:
            if grid[row][col] is not None:
                return "impossible"  # 同位置多个命名点
            grid[row][col] = name
    
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    
    def dfs(start_row, start_col, target_row, target_col, current_name):
        # 到达目标点
        if start_row == target_row and start_col == target_col:
            return True
        # 标记当前点为路径（临时占用）
        grid[start_row][start_col] = 'used'
        
        for dr, dc in directions:
            nr, nc = start_row + dr, start_col + dc
            if 0 <= nr < h and 0 <= nc < w:
                # 可以走的情况：空白，或者目标点
                if grid[nr][nc] is None or (nr == target_row and nc == target_col):
                    if dfs(nr, nc, target_row, target_col, current_name):
                        return True
        # 回溯：恢复当前点为空白
        grid[start_row][start_col] = None
        return False
    
    # 处理每一对同名点
    for name, points in name_points.items():
        # 两两配对处理
        for i in range(0, len(points), 2):
            start = points[i]
            end = points[i+1]
            # 恢复起点和终点的名称
            grid[start[0]][start[1]] = name
            grid[end[0]][end[1]] = name
            # 寻找路径
            if not dfs(start[0], start[1], end[0], end[1], name):
                return "impossible"
            # 标记路径为已占用（避免后续路径交叉）
            grid[start[0]][start[1]] = name
            grid[end[0]][end[1]] = name
    
    return "possible"


data = [
    (3, 3, [(1, 2, 'A'), (1, 3, 'B'), (3, 2, 'C'), (3, 1, 'D')]), # 调整h为3，适配坐标范围
    (3, 3, [(2, 1, 'A'), (3, 2, 'A')]), # 调整h为3，适配坐标范围
    (3, 4, [(2, 4, 'A'), (1, 1, 'B'), (1, 2, 'A'), (3, 1, 'B')]), # 调整h为3、w为4，适配坐标范围
    (3, 4, [(3, 4, 'A'), (2, 1, 'A'), (1, 2, 'B'), (3, 3, 'B')]) # 调整h为3、w为4，适配坐标范围
]

for row in data:
    h, w, named_vertices = row
    result = is_possible_to_connect(h, w, named_vertices)
    print(result)

修复后测试结果 #

impossible
possible
possible
impossible

与预期输出一致。

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