我在解决 Google 的 foobar challenge.I' 级别 4 时遇到了一些问题，我不明白我们是如何获得路径矩阵的

Question

我不需要任何code.Just解释我的问题（特别是路径矩阵）。这是问题：

你和你获救的兔子囚犯需要逃离 space 空间站这个坍塌的死亡陷阱——而且要快！不幸的是，有些兔兔因为长时间的禁锢而变得虚弱，不能运行跑得很快。他们的朋友正在努力帮助他们，但如果你也参与进来，这次逃跑会快很多。防御舱壁门已经开始关闭，如果你不及时通过，你就会被困住！你需要抓住尽可能多的兔子，并在它们关闭之前穿过舱壁。

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

除了花时间在兔子之间穿梭外，一些路径还与 space 站的安全检查站交互并使时间倒流。为时钟增加时间将延迟舱壁门的关闭，如果在门已经关闭后时间回到 0 或正数，则会触发舱壁重新打开。因此，也许可以绕着圈走，不断获得时间：也就是说，每走一条路，使用或增加的时间都是一样的。

写一个 answer(times, time_limit) 形式的函数来计算你能捡起的兔子数量以及它们是哪些兔子，同时仍然在门永远关闭之前通过舱壁逃脱。如果有多组相同大小的兔子，return 具有最低囚犯 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。这是此 space 车站走廊的最佳组合，因此答案是 [1, 2]。

Answer 1

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

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

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

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

第一行始终是起点。它告诉你从起点到任何其他点（兔子，舱壁）对关闭时间的影响
然后是兔子的行，示例中的第二行告诉您从兔子 #0 的位置到任何其他点等的时间影响。
终于有了从舱壁到其他点的路径

解决问题的一些提示：

如果图中有一个负循环，你可以带着所有的兔子逃跑，因为你只需要 return 一组被救出的兔子......你可以在负循环时立即退出检测到循环！
如果没有，那么你最好考虑一下 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.

结束于舱壁

让我们看一下示例并明确增量和 time_limit 更新。最佳方案是走以下路径（增量仅来自矩阵系数）：

开始 --> 舱壁：成本是 time[0][4] # == -1 所以 time_limit = 1 - (-1) = 2
Bulkhead --> Bunny #1：成本是 time[4][2] # == 2 所以 time_limit = 2 - 2 = 0
Bunny #1 --> Bulkhead：成本是 time[2][4] # == -1 所以 time_limit = 0 - (-1) = 1（Bunny #1 逃脱）
Bulkhead --> Bunny #2：成本是 time[4][3] # == 2 所以 time_limit = 1 - 2 = -1（Bulkhead 关闭因为 time_limit 变为负值）
Bunny #2 --> Bulkhead：成本是 time[3][4] # == -1 所以 time_limit = -1 - (-1) = 0（Bulkhead 重新打开，你和 Bunny #2 一起逃脱）

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

我在解决 Google 的 foobar challenge.I' 级别 4 时遇到了一些问题，我不明白我们是如何获得路径矩阵的

I'm having some trouble while solving Google's foobar challenge.I'm at level 4 and I'm not getting how did we get the path matrix

algorithm

graph-theory

matrix

data-structures