У меня возникли проблемы при решении проблемы Google с foobar. Я на 4-м уровне и не понимаю, как мы получили матрицу путей

Question

Я не хочу никакого кода. Просто объясните мне вопрос (особенно матрицу пути). Вот вопрос:

Вы и ваши спасенные заключенные зайчики должны выбраться из этой разрушающейся смертельной ловушки космической станции - и быстро! К сожалению, некоторые из кроликов были ослаблены их длительным заключением и не могут бежать очень быстро. Их друзья пытаются помочь им, но этот побег будет намного быстрее, если вы тоже разбьетесь. Двери защитной перегородки начали закрываться, и если вы не успеете вовремя, вы попадете в ловушку! Вам нужно захватить как можно больше кроликов и пройти через переборки, прежде чем они закроются.

Время, необходимое для перехода от вашей начальной точки ко всем кроликам и переборке, будет дано вам в квадратной матрице целых чисел. В каждом ряду будет указано время, необходимое для начала: первый кролик, второй кролик, ..., последний кролик и переборка в указанном порядке. Порядок строк соответствует одному и тому же шаблону (начало, каждый кролик, переборка). Кролики могут запрыгнуть в ваши руки, поэтому их можно забрать мгновенно, а прибытие к переборке в то же время, когда она запечатывает, позволяет успешно, хотя и драматично, сбежать. (Не волнуйтесь, любые кролики, которых вы не подберете, смогут сбежать с вами, так как им больше не придется нести те, которые вы подобрали.) Вы можете посетить другие места, если хотите, и перейти к переборке. не означает, что вы должны немедленно уйти - вы можете двигаться к переборке и обратно, чтобы забрать дополнительных кроликов, если позволит время.

Помимо путешествий между кроликами, некоторые пути взаимодействуют с контрольными точками безопасности космической станции и добавляют время к часам. Добавление времени к часам задержит закрытие дверей переборки, и если время возвращается к 0 или положительному числу после того, как двери уже закрыты, это вызывает переборку, чтобы открыть снова. Следовательно, может быть возможно ходить по кругу и продолжать выигрывать время: то есть каждый раз, когда путь проходит, используется или добавляется одно и то же количество времени.

Напишите функцию в форме ответа (times, time_limit), чтобы вычислить наибольшее количество кроликов, которых вы можете подобрать, и какие они являются кроликами, при этом все еще убегая через переборку до того, как двери закрываются навсегда. Если имеется несколько наборов кроликов одинакового размера, верните набор кроликов с наименьшими идентификаторами заключенных (в виде индексов) в отсортированном порядке. Кролики представлены в виде отсортированного списка по идентификатору заключенного, причем первый кролик равен 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

Давайте смоделируем проблему, используя теорию графов. Положение каждой интересующей точки (начало, каждый кролик, переборка) можно рассматривать как вершину. Прямой путь от каждой из этих точек к другой будет взвешенным ребром в графе.

Как видите, у нас здесь плотный граф, поскольку существует прямой путь, который напрямую соединяет любые две точки интереса.

Матрица просто сообщает вам относительную стоимость во времени для закрытия переборки (путь может иметь отрицательный вес, если он добавляет больше времени до закрытия переборки, чем фактическое время, необходимое для его прохождения). Это означает, что это матрица смежности, моделирующая граф, который мы определили выше.

Таким образом, каждая строка матрицы представляет пути из одной точки в другую:

• Первый ряд всегда является отправной точкой. Он говорит вам влияние на время закрытия, чтобы перейти от начальной точки к любой другой точке (кролики, переборка)
• Затем идут строки для кроликов, вторая строка в вашем примере говорит о временном воздействии для перехода из положения кролика № 0 в любую другую точку и так далее.
• Наконец у вас есть пути от переборки до других точек

Некоторые советы по решению проблемы:

• Если на графике есть отрицательный цикл, вы можете сбежать со всеми кроликами, и поскольку вам нужно только вернуть набор спасенных кроликов... Вы можете выйти, как только будет обнаружен отрицательный цикл!
• Если нет, тогда вам лучше подумать о Беллмане -Форде и посмотреть, к чему это вас ведет (хорошо, что алгоритм Беллмана-Форда также можно использовать для обнаружения отрицательных циклов!)

---

РЕДАКТИРОВАТЬ: объяснение логики позади матрицы

Чтобы увидеть, как это работает, давайте развернем данный пример:

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
• Переборка -> Кролик #1: стоимость time[4][2] # == 2 так time_limit = 2 - 2 = 0
• Кролик № 1 -> Переборка: стоимость time[2][4] # == -1 так time_limit = 0 - (-1) = 1 (Кролик № 1 сбегает)
• Переборка -> Кролик #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] (Идентификаторы кролика № 1 и кролика № 2, отсортированные в порядке возрастания в соответствии с описанием проблемы).