我在解决谷歌的foobar挑战时遇到了一些麻烦。我处于 4 级，我不明白我们如何获得路径矩阵

Question

我不想要任何代码。

您和您被救出的兔子囚犯需要摆脱空间站的倒塌死亡陷阱 - 快速！不幸的是，其中一些兔子的长期监禁削弱了，不能很快运行。他们的朋友正在尝试帮助他们，但是如果您也参与进来，这种逃生将会更快。防御性的舱壁门已经开始关闭，如果您不及时完成，您将被困！您需要尽可能多地抓住兔子，并在关闭舱壁之前浏览它们。

从您的起点转移到所有兔子和舱壁的时间将以整数的正方形矩阵给予您。每行都会告诉您开始开始的时间，第一个兔子，第二个兔子，...，最后一个兔子和舱壁。行的顺序遵循相同的模式(开始，每个兔子，舱壁(。兔子可以跳入您的手臂，因此将它们捡起是瞬时的，并且同时到达舱壁，因为它密封仍然可以成功(如果戏剧性(逃脱。(不用担心，任何您不捡到的兔子都可以与您逃脱并不意味着您必须立即离开 - 如果时间允许，您可以搬到舱壁上捡起其他兔子。

除了花费时间在兔子之间旅行外，一些路径还与空间站的安全检查点相互作用，并将时间添加回时钟。在时钟上增加时间将延迟舱壁门的关闭，如果时间返回到0或在门已经关闭后的正数或正数，它会触发舱壁重新打开。因此，可能有可能走进一个圆圈并继续增加时间：也就是说，每次穿越路径时，使用或添加了相同的时间。

写一个表单答案的函数(times，time_limit(，以计算您可以捡起的最多兔子和它们是哪些兔子，同时仍在门上闭合之前逃脱了舱壁。如果有多组相同大小的兔子，请按顺序返回具有最低囚犯ID(作为索引(的兔子。兔子被囚犯ID表示为排序清单，第一个兔子为0。最多有5个兔子，而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，五个内部阵列行指定起点，兔子0，兔子1，兔子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

让我们使用图理论对问题进行建模。每个兴趣点的位置(开始，每个兔子，舱壁(可以将其视为顶点。从每个点到另一个点的直接路径将是图中的加权边缘。

您可以看到，我们在这里有一个密集的图，因为有一个直接连接任意两个兴趣点的直接路径。

矩阵只是告诉您与舱壁关闭的相对成本(如果路径在闭合舱面之前的添加时间比走路所需的实际时间更高的时间(。这意味着它是邻接矩阵建模我们上面定义的图。

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

• 第一行始终是起点。它告诉您对从起点到其他任何点(Bunnies，Bulkhead(的关闭时间的影响
• 然后来到兔子的行，示例中的第二行告诉您从兔子＃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
]

三角洲仅来自相关矩阵系数。每当您使用给定的delta走路时，您都必须相应地更新time_limit：

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

如果time_limit严格为负，则舱壁关闭。如果它恢复到零(经过负路径(，则重新打开。问题要求您找到拯救最多兔子并与之逃脱的道路。这意味着这样的路径必须以time_limit >= 0的结尾。

让我们浏览示例，并说明Deltas和time_limit更新。最好的情况是走下以下路径(三角洲仅来自矩阵系数(：

• 开始 -> Bulkhead：成本为time[0][4] # == -1 SO time_limit = 1 - (-1) = 2
• Bulkhead->兔子＃1：成本是time[4][2] # == 2 SO time_limit = 2 - 2 = 0
• Bunny＃1-> Bulkhead：成本为time[2][4] # == -1 SO time_limit = 0 - (-1) = 1(Bunny＃1 Escapes(
• Bulkhead->兔子＃2：成本为time[4][3] # == 2 SO time_limit = 1 - 2 = -1(隔板关闭，因为time_limit变为负(
• Bunny＃2-> Bulkhead：成本是time[3][4] # == -1 SO time_limit = -1 - (-1) = 0(Bulkhead重新开放，您可以使用兔子＃2逃脱(

因此，被救出的兔子集为 [1, 2](兔子＃1和兔子＃2 ID，按照问题描述要求按要求进行排序(。