#coding=utf-8
#输出路径结果，二维数组，每一个元素为一个路径数组
wayList = []

#在该方法中完成遍历算法，找出每一条通向终点或不通的路径，并将遍历到的每一条有效路径序号生成一个数组，然后将数组放入wayList数组中
#比如0-2-3和0-1-3两条路径，则将[0,2,3]和[0,1,3]两个数组放入wayList
# nodeCount:抽象图中的节点总数量
# costs:二维权值数组，表示序号0~nodeCount节点之间的权值关系，元素为int类型，比如使用data.costs[0][2]获得第一个节点和第三个节点之间的权值
# startIndex:起始节点序号
# endIndex:终点节点序号
def FindPath(nodeCount, costs, startIndex, endIndex):
    # 存储路径的列表
    paths = []

    # 存储已访问过的节点
    visited = set()

    # 深度优先搜索函数
    def dfs(node, path):
        # 将当前节点加入路径
        path.append(node)
        # 标记当前节点为已访问
        visited.add(node)

        # 如果当前节点为终点或者堵点，则将路径添加到 paths 中
        if node == endIndex or (node != endIndex and sum(1 for cost in costs[node] if cost > 0) <= 1):
            paths.append(list(path))
        else:
            # 遍历当前节点的邻居节点
            for neighbor, cost in enumerate(costs[node]):
                # 如果邻居节点未访问过且当前节点与邻居节点相通
                if neighbor not in visited and cost > 0:
                    # 递归搜索
                    dfs(neighbor, path)
        
        # 回溯，将当前节点从路径中删除，同时标记为未访问
        path.pop()
        visited.remove(node)

    # 开始深度优先搜索
    dfs(startIndex, [])

    # 将路径添加到 wayList 中
    for path in paths:
        wayList.append(path)

    return wayList