问题描述

我在 google foobar 挑战的第 4 级。我在这个问题上面临问题。我已经在提供的测试用例上尝试了我的解决方案，但谷歌的成绩检查器显示我的代码对于这些测试用例也是错误的。有谁能够帮我？我到底错在哪里？

问题

逃生舱

给定兔子组的起始房间号，逃生舱的房间号，以及在其间的每条走廊的每个方向上一次可以容纳多少只兔子，计算出有多少只兔子可以安全地逃生在高峰期一次豆荚。

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

例如，如果您有：

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 向 2 发送 4/4 兔子，向 3 发送 6/6 兔子 1 向 2 发送 4/5 兔子，向 3 发送 2/2 兔子 2 向 4 发送 4/4 兔子， 4/4 兔子到 5 3 发送 4/6 兔子到 4 和 4/6 兔子到 5

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

测试用例

您的代码应通过以下测试用例。请注意，它也可能针对此处未显示的隐藏测试用例运行。

-- Python 案例 -- 输入：

solution.solution([0], [3], [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]])

输出：

输入：

solution.solution([0, 1], [4, 5], [[0, 0, 4, 6, 0, 0], [0, 0, 5, 2, 0, 0], [0, 0, 0, 0, 4, 4], [0, 0, 0, 0, 6, 6], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]])

输出：

我的解决方案

def get_new_path(entrances,exits,path):
    for p in path:
        p.insert(0, 0)
        p.append(0)
    new_length = len(path[0])
    path.insert(0,[0]* new_length)
    path.append([0]* new_length)
    for e in entrances:
        path[0][e+1] = 2e+6
    for e in exits:
        path[e+1][new_length-1] =  2e+6
    return path

def get_route(stack, open, path):
    next = stack[-1]
    list_of_nexts = [i for i,val in enumerate(path[next]) if ( i not in open and val != 0)]
    for i in list_of_nexts:
        open.add(i)
    if len(path)-1 in list_of_nexts:
        stack.append(len(path)-1)
        return stack
    for i in list_of_nexts:
        new_stack = stack.copy()
        new_stack.append(i)
        r = get_route(new_stack, open, path)
        if r == -1: continue
        else: return r
    return -1
    
def solution(entrances, exits, path):
    path = get_new_path(entrances, exits, path)
    flow = 0
    while True:
        stack = [0]
        open = set()
        open.add(0)
        route = get_route(stack, open, path)
        if(route == -1):
            return flow
        else:
            f = min([path[route[i-1]][route[i]] for i in range(1,len(route))])
            for i in range(2,len(route)-1):
                temp = path[route[i-1]][route[i]]
                path[route[i-1]][route[i]] = temp - f
                path[route[i]][route[i-1]] += f
            flow += f    
    return flow

print(solution([0, 1], [4, 5], [[0, 0, 4, 6, 0, 0], [0, 0, 5, 2, 0, 0], [0, 0, 0, 0, 4, 4], [0, 0, 0, 0, 6, 6], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]))

标签： pythonarraysalgorithmdepth-first-searchmax-flow

python - Escape Pods Google Foobar 挑战 | 最大流量问题

问题描述

问题

逃生舱

测试用例

我的解决方案

解决方案

推荐阅读