我正在解决第 4 级的 Google Foobar - Escape pods 问题，我在测试用例 N.4 上遇到了一个从未通过的问题！我距离截止日期只有两天的时间，无法弄清楚我的代码在这种情况下有什么问题。有没有人可以看看或可以为我提供一些我的代码失败的测试用例？这是问题：

逃生舱

您已经炸毁了 LAMBCHOP 世界末日装置并将兔子从 Lambda 的监狱中解救出来 - 现在您需要尽可能快速有序地逃离空间站！兔子们都聚集在车站的不同位置，需要前往车站其他地方看似无穷无尽的逃生舱。您需要通过各个房间将众多兔子带到逃生舱。不幸的是，房间之间的走廊一次只能容纳这么多兔子。更重要的是，许多走廊的大小都经过调整以容纳 LAMBCHOP，因此它们一次可以穿过的兔子数量各不相同。

给定兔子组的起始房间号，逃生舱的房间号，以及中间每个走廊的每个方向一次可以通过的兔子数量，计算出有多少兔子可以安全地逃生豆荚在高峰期。

编写一个函数解决方案（入口、出口、路径），它采用表示聚集的兔子组所在位置的整数数组、表示逃生舱所在位置的整数数组以及走廊整数数组的数组，以整数形式返回每个时间步可以通过的兔子总数。入口和出口是不相交的，因此永远不会重叠。路径元素 path[A][B] = C 描述了从 A 到 B 的走廊在每个时间步都可以容纳 C 个兔子。最多有 50 个房间由走廊连接，最多可以容纳 2000000 只兔子。

For example, if you have:
entrances = [0, 1]
exits = [4, 5]
path = [
  [0, 0, 4, 6, 0, 0],  # Room 0: Bunnies
  [0, 0, 5, 2, 0, 0],  # Room 1: Bunnies
  [0, 0, 0, 0, 4, 4],  # Room 2: Intermediate room
  [0, 0, 0, 0, 6, 6],  # Room 3: Intermediate room
  [0, 0, 0, 0, 0, 0],  # Room 4: Escape pods
  [0, 0, 0, 0, 0, 0],  # Room 5: Escape pods
]

然后在每个时间步中，可能会发生以下情况： 0 将 4/4 兔子发送给 2，将 6/6 兔子发送给 3 1 将 4/5 兔子发送给 2 和 2/2 兔子给 3 2 将 4/4 兔子发送给 4 和4/4 兔子给 5 3 送 4/6 兔子给 4 和 4/6 兔子给 5

因此，在每个时间步长 4 和 5 时，总共有 16 只兔子可以到达逃生舱。（请注意，在此示例中，房间 3 可以将 8 只兔子的任何变体发送给 4 和 5，例如 2/6 和 6/6，但最终解决方案保持不变。）

这是我的代码：

class Edge:
    def __init__(self, destination, capacity):
        self.destination = destination
        self.capacity = capacity
        self.remaining = capacity


class Node:

    def __init__(self, name, level=0, edges=None):
        self.name = name
        self.level = level
        if edges is None:
            self.edges = []

    def add_edge(self, destination, weight):
        self.edges.append(Edge(destination, weight))

    def get_children(self):
        res = []
        for edge in self.edges:
            res.append(edge.destination)
        return res

    def __str__(self):
        res = str(self.name) + " ({})".format(str(self.level))
        for edge in self.edges:
            res = res + " --> {} ({})".format(str(edge.destination), str(edge.remaining))
        return res


class Graph:
    nodes = []
    flow = []
    permanent_dead_ends = []
    levels = []

    def __init__(self, entrances, exits, matrix):
        self.entrances = entrances
        self.exits = exits
        self.matrix = matrix
        for i in range(0, len(self.matrix)):
            self.nodes.append(Node(i))

    def create(self):
        for i in range(0, len(self.matrix)):
            if self.nodes[i].name in self.exits:
                continue
            for j in range(0, len(self.matrix[i])):
                if self.matrix[i][j] != 0:
                    self.nodes[i].add_edge(j, self.matrix[i][j])

    def bfs(self):
        queue = self.entrances[:]
        seen = self.entrances[:]
        level = 0
        self.levels = [-1] * len(self.matrix)
        for entrance in self.entrances:
            self.nodes[entrance].level = level
            self.levels[entrance] = level
        while len(queue) > 0:
            to_remove = []
            i = queue.pop(0)
            level = self.nodes[i].level + 1
            for edge in self.nodes[i].edges:
                if edge.destination in self.permanent_dead_ends:
                    to_remove.append(edge)   # pruning permanent dead ends
                elif edge.remaining > 0:
                    if edge.destination not in seen:
                        self.nodes[edge.destination].level = self.levels[edge.destination] = level
                        queue.append(edge.destination)
                        seen.append(edge.destination)
                else:
                    to_remove.append(edge)
            for edge in to_remove:
                self.nodes[i].edges.remove(edge)

        #for node in self.nodes:
            #print(node)

        if self.is_finished():
            return False

        return True

    def is_finished(self):
        for ex in self.exits:
            if self.levels[ex] != -1:
                return False
        return True

    def choose_next_node(self, candidates, dead_ends):
        for i in candidates:
            previous_level = self.nodes[i].level
            for edge in self.nodes[i].edges:
                if (edge.remaining > 0) \
                        and (previous_level < self.nodes[edge.destination].level)\
                        and (edge.destination not in dead_ends):
                    return i, edge, edge.remaining
        return None, None, None

    def dfs(self):
        path = []
        capacities = []
        edges = []
        dead_ends = self.permanent_dead_ends[:]
        entr = self.entrances[:]
        current_node, edge, capacity = self.choose_next_node(entr, dead_ends)
        next_node = None
        if edge is not None:
            next_node = edge.destination
            edges.append(edge)
            path.append(current_node)
            if next_node in self.exits:
                path.append(next_node)
                capacities.append(capacity)
        else:
            return

        while next_node not in self.exits and len(path) > 0:
            if next_node != path[-1]:
                path.append(next_node)
                capacities.append(capacity)
            current_node, edge, capacity = self.choose_next_node([next_node], dead_ends)
            if edge is not None:
                next_node = edge.destination
                edges.append(edge)
                if next_node in self.exits:
                    path.append(next_node)
                    capacities.append(capacity)
            else:
                #print("dead-end reached: {}".format(path))
                if len(path) > 1:
                    dead_ends.append(path[-1])
                    path = path[:-1]
                    edges = edges[:-1]
                    next_node = path[-1]
                    capacities = capacities[:-1]
                else:
                    entr.remove(path[0])
                    path = []
                    capacities = []
                    current_node, edge, capacity = self.choose_next_node(entr, dead_ends)
                    next_node = None
                    if edge is not None:
                        next_node = edge.destination
                        edges.append(edge)
                        path.append(current_node)
                        if next_node in self.exits:
                            path.append(next_node)
                            capacities.append(capacity)
                    else:
                        return

        if len(path) < 1:
            #print("no path found!")
            return False

        capacity = min(capacities)
        #print("capacity: {}".format(capacity))
        self.flow.append(capacity)
        #print("path: {}".format(path))
        i = 0
        for edge in edges:
            edge.remaining -= capacity
            if edge.remaining == 0:
                self.nodes[path[i]].edges.remove(edge)
                if len(self.nodes[path[i]].edges) < 1:
                    self.permanent_dead_ends.append(self.nodes[path[i]].name)
                    #print("added permanent dead end: {}".format(self.nodes[path[i]].name))
            i += 1
        #for node in self.nodes:
            #print(node)

        return False


def solution(entrances, exits, matrix):
    graph = Graph(entrances,  exits, matrix)
    graph.create()
    while graph.bfs():
        #print("another BFS!")
        graph.dfs()
    #print("flow is: {}".format(graph.flow))
    return sum(graph.flow)