递归查找所有可行坐标路径：邻接规则下的路径生成需求

首先明确问题：我们要从给定的坐标点列表里找出所有符合规则的路径——路径里相邻两点的x、y坐标差绝对值都不超过1（斜着挨着也算），路径可以从任意点开始，且每个点在同一条路径里只能出现一次（否则会有无限循环的路径）。

实现步骤 #

• 预处理坐标点：把列表里的坐标转成元组（方便作为字典键和集合元素），同时生成一个集合用于快速判断点是否存在。
• 构建邻接表：给每个点找出所有符合邻接规则的其他点，存成字典，这样遍历的时候不用每次都全量检查所有点。
• DFS遍历所有路径：用深度优先搜索从每个点出发，递归遍历所有可能的路径，记录已访问的点避免重复，回溯时恢复状态。
• 收集结果：把所有生成的路径收集起来，按需输出。

Python代码 #

# 原始坐标点
coords = [[4, 5], [4, 6], [5, 6], [5, 4], [6, 5], [7, 5]]
# 转成元组方便操作
coord_tuples = [tuple(pt) for pt in coords]
coord_set = set(coord_tuples)

# 构建每个点的邻接点映射
adj_map = {}
for pt in coord_tuples:
    x, y = pt
    neighbors = []
    for other_pt in coord_tuples:
        if other_pt == pt:
            continue
        ox, oy = other_pt
        # 判断是否符合邻接规则
        if abs(x - ox) <= 1 and abs(y - oy) <= 1:
            neighbors.append(other_pt)
    adj_map[pt] = neighbors

all_valid_paths = []

# DFS递归函数
def traverse_paths(current_pt, visited, current_path):
    # 把当前路径加入结果集
    all_valid_paths.append(current_path.copy())
    # 遍历所有邻接点
    for neighbor in adj_map[current_pt]:
        if neighbor not in visited:
            visited.add(neighbor)
            current_path.append(neighbor)
            traverse_paths(neighbor, visited, current_path)
            # 回溯：移除当前点，恢复状态
            current_path.pop()
            visited.remove(neighbor)

# 从每个点开始遍历所有可能的路径
for start_pt in coord_tuples:
    visited_points = set()
    visited_points.add(start_pt)
    traverse_paths(start_pt, visited_points, [start_pt])

# 输出结果
print("所有可行路径：")
for i, path in enumerate(all_valid_paths, 1):
    print(f"路径 {i}: {path}")

代码说明 #

• 邻接表：提前构建好每个点的邻接点，避免每次遍历都重复计算，提升效率。
• DFS回溯：通过递归遍历每个分支，回溯时恢复已访问集合和当前路径，确保所有可能的路径都被覆盖。
• 结果包含单点路径：如果不需要单点路径，可以在all_valid_paths.append前加判断if len(current_path) >= 2。

部分输出示例 #

路径 1: [(4, 5)]
路径 2: [(4, 5), (4, 6)]
路径 3: [(4, 5), (4, 6), (5, 6)]
路径 4: [(4, 5), (5, 4)]
路径 5: [(4, 5), (6, 5)]
路径 6: [(4, 5), (6, 5), (7, 5)]
路径 7: [(4, 6)]
路径 8: [(4, 6), (4, 5)]
路径 9: [(4, 6), (4, 5), (5, 4)]
...

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