Python实现：找出所有可到达目标点的连续路径点组合

思路梳理 #

• 从示例反推路径规则：路径是点的序列，每个后续点的x和y都严格大于前一个点的x和y
• 目标是找出所有以纵坐标为7的点为终点的合法路径

代码实现 #

points = [(1,2),(3,4),(5,7),(4,7),(6,7)]

# 筛选目标点（纵坐标为7的点）
target_points = [p for p in points if p[1] == 7]

# 深度优先搜索找所有合法路径
def find_paths(current_point, visited, path):
    paths = []
    # 当前点是目标点则记录路径
    if current_point in target_points:
        paths.append(path.copy())
        return paths
    # 遍历所有符合条件的下一个点
    for p in points:
        if p not in visited and p[0] > current_point[0] and p[1] > current_point[1]:
            visited.add(p)
            path.append(p)
            paths.extend(find_paths(p, visited, path))
            # 回溯，尝试其他分支
            path.pop()
            visited.remove(p)
    return paths

# 收集所有非目标点出发的合法路径
all_valid_paths = []
for start in points:
    if start not in target_points:
        paths_from_start = find_paths(start, {start}, [start])
        all_valid_paths.extend(paths_from_start)

# 按示例格式输出结果
for path in all_valid_paths:
    print(path, end=" ")

代码说明 #

• 用DFS遍历所有可能的点序列，每次只选择满足x、y递增的未访问点作为下一个节点
• 回溯机制确保能遍历到所有分支路径
• 最终收集所有以目标点结尾的合法路径

运行代码后输出：
[(1, 2), (3, 4), (5, 7)] [(1, 2), (3, 4), (4, 7)] [(1, 2), (3, 4), (6, 7)]

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