如何从迷宫二维数组生成指定格式的Edge List

核心思路 #

要生成目标格式的Edge List，我们需要：

• 遍历迷宫中的每一个非墙体方格
• 检查每个方格的相邻方格（可选择4方向或8方向移动）
• 为每对相邻的有效路径方格创建一条边记录
• 避免重复记录同一条边（如['B1','B2',1]和['B2','B1',1]视为同一条边）

完整代码实现 #

# 定义迷宫二维列表
mazelst = [
    ['***', '***', '***', '***', '***', '***', '***', '***', '***', '***', '***', '***'],
    ['***', 'B1', 'B2', 'B3', '***', 'B5', 'B6', '***', 'B8', 'B9', 'End', '***'],
    ['***', 'C1', '***', 'C3', 'C4', 'C5', 'C6', '***', 'C8', '***', '***', '***'],
    ['***', 'D1', 'D2', '***', 'D4', '***', 'D6', '***', 'D8', '***', 'D10', '***'],
    ['***', '***', 'E2', '***', '***', '***', 'E6', '***', 'E8', 'E9', 'E10', '***'],
    ['***', 'F1', 'F2', 'F3', 'F4', 'F5', 'F6', 'F7', 'F8', '***', 'F10', '***'],
    ['***', 'Start', '***', '***', 'G4', 'G5', 'G6', '***', 'G8', 'G9', 'G10', '***'],
    ['***', '***', '***', '***', '***', '***', '***', '***', '***', '***', '***', '***']
]

rows = len(mazelst)
cols = len(mazelst[0]) if rows > 0 else 0

# 定义相邻方格偏移量：4方向（上下左右），如需8方向可替换为注释里的列表
offsets = [(-1,0), (1,0), (0,-1), (0,1)]
# offsets = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

def inBoard(r, c):
    """检查坐标是否在迷宫范围内"""
    return 0 <= r < rows and 0 <= c < cols

def getNeighbours(r, c):
    """获取指定坐标的所有有效相邻坐标"""
    return [(r+v, c+h) for v, h in offsets if inBoard(r+v, c+h)]

# 生成Edge List
edge_list = []
seen_edges = set()  # 用于去重

for r in range(rows):
    for c in range(cols):
        current_node = mazelst[r][c]
        if current_node == '***':
            continue  # 跳过墙体
        
        # 遍历当前节点的所有相邻方格
        for nr, nc in getNeighbours(r, c):
            neighbor_node = mazelst[nr][nc]
            if neighbor_node == '***':
                continue  # 跳过相邻墙体
            
            # 用排序后的元组记录已存在的边，避免重复
            edge_key = tuple(sorted((current_node, neighbor_node)))
            if edge_key not in seen_edges:
                seen_edges.add(edge_key)
                edge_list.append([current_node, neighbor_node, 1])

# 可选：对Edge List按节点名称排序，提升可读性
edge_list.sort()

# 打印结果（按目标格式输出）
print("[")
for edge in edge_list:
    print(f"  {edge},")
print("]")

代码说明 #

• 迷宫定义：直接使用你提供的二维迷宫列表，'***'代表墙体，其他字符串为路径节点。
• 偏移量选择：默认使用4方向移动（上下左右），如果需要支持对角线移动，只需替换offsets变量为8方向的偏移列表。
• 去重机制：通过seen_edges集合存储已记录的边（以排序后的元组形式），确保每条边只被记录一次。
• 结果格式：最终生成的edge_list完全符合你要求的格式，每条边以[节点1, 节点2, 1]的形式存储。

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