algorithm - 我在解决 Google 的 foobar 挑战时遇到了一些麻烦。我处于第 4 级，但我不知道我们是如何获得路径矩阵的

Question

关闭。这个问题需要更多 focused .它目前不接受答案。












想改进这个问题？更新问题，使其仅关注一个问题 editing this post .

1年前关闭。




Improve this question




我不想要任何代码。只需向我解释这个问题( 尤其是路径矩阵 )。这是问题:

你和你获救的兔子囚犯需要摆脱这个空间站崩溃的死亡陷阱——而且要快!不幸的是，一些兔子因长期监禁而变得虚弱，不能跑得很快。他们的 friend 正在努力帮助他们，但如果你也投入其中，这次逃跑会更快。防御舱壁门已经开始关闭，如果你不及时通过，你会被困住!您需要尽可能多地捕获兔子并在它们关闭之前穿过舱壁。

从您的起点移动到所有兔子和舱壁所需的时间将以整数方阵的形式提供给您。每一行都会告诉你到达开始所需要的时间，第一只兔子，第二只兔子，...，最后一只兔子，以及按顺序排列的隔板。行的顺序遵循相同的模式(开始，每个兔子，隔板)。兔子可以跳进你的怀抱，因此可以立即将它们捡起来，并且在密封的同时到达舱壁仍然可以成功逃脱，即使是戏剧性的逃脱。 (别担心，任何你没有捡到的兔子都可以和你一起逃跑，因为它们不再需要携带你捡到的兔子。)如果你愿意，你可以重新访问不同的地方，然后移动到舱壁并不意味着您必须立即离开 - 如果时间允许，您可以往返于舱壁以捡起更多的兔子。

除了花时间在兔子之间旅行之外，一些路径还与空间站的安全检查站交互，并将时间加回时钟。向时钟添加时间将延迟舱壁门的关闭，如果在门已经关闭后时间回到 0 或正数，则会触发舱壁重新打开。因此，有可能绕着一个圈走并不断获得时间:也就是说，每次经过一条路径，都会使用或增加相同的时间。

编写一个形式为 answer(times, time_limit) 的函数来计算您可以捡起的最多兔子以及它们是哪些兔子，同时在门永远关闭之前仍然通过舱壁逃生。如果有多个相同大小的兔子集，则按排序顺序返回具有最低囚犯 ID(作为索引)的兔子集。 bunnies 表示为一个按囚犯 ID 排序的列表，第一个 bunny 为 0。最多有 5 个 bunnies，time_limit 是一个非负整数，最多为 999。

例如，在

[
  [0, 2, 2, 2, -1],  # 0 = Start
  [9, 0, 2, 2, -1],  # 1 = Bunny 0
  [9, 3, 0, 2, -1],  # 2 = Bunny 1
  [9, 3, 2, 0, -1],  # 3 = Bunny 2
  [9, 3, 2, 2,  0],  # 4 = Bulkhead
]

时限为1，内五行分别指定起点、bunny 0、bunny 1、bunny 2、舱壁门导出。你可以走这条路:

Start End Delta Time Status
    -   0     -    1 Bulkhead initially open
    0   4    -1    2
    4   2     2    0
    2   4    -1    1
    4   3     2   -1 Bulkhead closes
    3   4    -1    0 Bulkhead reopens; you and the bunnies exit

使用此解决方案，您将拿起兔子 1 和 2。这是这个空间站走廊的最佳组合，因此答案是 [1, 2]。

Answer 1

让我们使用图论对问题进行建模。每个兴趣点(起点、每个兔子、舱壁)的位置可以被认为是一个顶点。从这些点中的每一个到另一个点的直接路径将是图中的加权边。

如您所见，我们在这里有一个密集图，因为有一条直接连接任何两个兴趣点的直接路径。

该矩阵只是告诉您关闭舱壁的相对时间成本(如果一条路径在关闭舱壁之前增加了比步行所需的实际时间更多的时间，则该路径的权重可能为负)。这意味着它是 邻接矩阵 对我们上面定义的图进行建模。

因此，矩阵的每一行代表从一个点到另一个点的路径:

第一行始终是起点。它告诉您从起点到任何其他点(兔子、舱壁)对关闭时间的影响

然后是兔子的行，示例中的第二行告诉您从兔子 #0 的位置到任何其他点的时间影响，依此类推。

最后你有从舱壁到其他点的路径

解决问题的一些提示:

如果图中有负循环，你可以带着所有的兔子逃跑，因为你只需要返回一组获救的兔子……一旦检测到负循环，你就可以退出!

如果没有，那么您最好考虑一下 Bellman-Ford，看看它会引导您(好在 Bellman-Ford 算法也可用于检测负循环!)

编辑:明确矩阵背后的逻辑

要了解它是如何工作的，让我们展开给定的示例:

time_limit = 1
times = [
    [0, 2, 2, 2, -1],  # 0 = Start
    [9, 0, 2, 2, -1],  # 1 = Bunny 0
    [9, 3, 0, 2, -1],  # 2 = Bunny 1
    [9, 3, 2, 0, -1],  # 3 = Bunny 2
    [9, 3, 2, 2,  0],  # 4 = Bulkhead
]

增量只是来自相关的矩阵系数。每次你走一 strip 有给定 delta 的路径时，您必须更新 time_limit因此:

delta = times[starting_point][ending_point]
time_limit = time_limit - delta

如果 time_limit变为严格负数，舱壁关闭。如果它回到零(通过负路径)，它会重新打开。该问题要求您找到拯救最多兔子并与它们一起逃脱的路径。这意味着这样的路径必须以 time_limit >= 0 结尾。 .

让我们看一下这个例子，并明确 delta 和 time_limit更新。
最好的情况是走以下路径(增量仅来自矩阵系数):

开始 --> 隔板:成本为 time[0][4] # == -1所以time_limit = 1 - (-1) = 2

隔板 --> Bunny #1:成本为 time[4][2] # == 2所以time_limit = 2 - 2 = 0

兔子 #1 --> 隔板:成本为 time[2][4] # == -1所以time_limit = 0 - (-1) = 1 (兔子#1 逃脱)

隔板 --> Bunny #2:成本为 time[4][3] # == 2所以time_limit = 1 - 2 = -1 (隔板关闭，因为 time_limit 变为负数)

兔子 #2 --> 隔板:成本为 time[3][4] # == -1所以time_limit = -1 - (-1) = 0 (隔板重新打开，你和兔子 #2 一起逃跑)

因此，获救兔子的集合是 [1, 2] (Bunny #1 和 Bunny #2 ID，按照问题描述的要求按升序排序)。