如何连接图中的点以使它们的路径不交叉？

Question

我正在研究一个算法问题。作为输入，我得到了定义的图表。每个点都有高度、宽度和一些有名称的点。

我的任务是确定所有点是否可以连接到另一个同名的点。他们的道路不能交叉。

你能帮我解决我的算法吗？我不明白为什么即使应该返回“可能”的输入仍然返回“不可能”

# 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)

预期输出： 不可能的 可能的 可能的 不可能

实际产量： 不可能的 不可能的 不可能的 不可能

我发现的唯一类似问题是这个，但它导致了疯狂的技术pdf理论分析。一定有更简单的方法。

Answer 1

返回不可能，因为测试数据点脱离网格。所以它退出于：

# Named vertex coordinates out of bounds

您要么想将 if 语句更改为

if 0 < row <= h and 0 < col <= w:
   ...

或减少命名顶点列表中点的坐标。