Решение проблемы с гниющими апельсинами с помощью JavaScript.

LeetCode #994 Rotting Oranges — действительно интригующая задача, в которую стоит сесть и разобраться.

Основная идея заключается в следующем: мы получаем сетку в качестве входных данных, и каждое значение равно 0, 1 или 2.

1 — свежие апельсины, 2 — гнилые апельсины, а 0 — пустые места.

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

Итак, давайте возьмем O-ICEy с этим…

Выходные данные: минимальное количество минут, которое должно пройти, пока ни в одной ячейке не останется свежего апельсина.

Входы: наш сад (сетка)

Ограничения:

  • м == сетка.длина
  • n == сетка[i].length
  • 1 ≤ m, n ≤ 10 (наконец-то ввод разумного размера от Leetcode!)

Пограничные случаи: поскольку мы уверены, что сетка имеет хотя бы какое-то измерение, я пока скажу н/д.

Вот краткий пример того, как выглядит эта прогрессия

Апельсин в [0, 0] приходит испорченным. Проходит одна минута, и соседние апельсины тоже испортились. Еще минута, и все апельсины, способные испортиться, испортились.

*Небольшое примечание: в этом конкретном примере мы бы фактически вернули -1, потому что еще остался свежий апельсин. Если бы апельсина в [2, 2] не было, ответом было бы 2.

Продумать проблему

Есть как минимум несколько подходов к этому. Это было мое-

Я хочу иметь способ взять фруктовый сад и смоделировать порчу, которая произойдет через одну минуту. Затем я хочу запустить этот цикл несколько раз, пока не останется соседних апельсинов, которые можно испортить. Мне казалось, что самым чистым решением было рекурсивное

* есть вспомогательные функции, которые в настоящее время не показаны в аннотации (isDuplicate, adjacencies, adjacenciesRemain и emptyOrchard). Я включу их в окончательное решение.

После вызова cycleOranges ускорит наши апельсины через циклы порчи, увеличивая при этом секундомер. Это даст нам, сколько минут прошло, прежде чем все апельсины, способные испортиться, испортились.

После этого (строка 30) я проверяю, действительно ли наш секундомер зафиксировал время и что сад «пустой», а это означает, что все присутствующие апельсины испортились. Независимо от времени нашего секундомера, если в сетке все еще есть свежие апельсины, возвращается -1.

Вот полное решение:

Сводка

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

Сначала грубая сила, потом уточнения.

Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter и LinkedIn. Присоединяйтесь к нашему сообществу Discord.