Rotting Oranges

Средняя№994сетка

В сетке есть пустые клетки, свежие апельсины и гнилые. Каждую минуту гнилой апельсин портит соседние свежие: сверху, снизу, слева и справа. Нужно найти, сколько минут пройдёт, пока не останется свежих, или -1, если какие-то не сгниют никогда. Наш пример: RFF. / F.FF / FF.R (R — гнилой, F — свежий, . — пусто) — ответ 3.

994 Rotting OrangesРазбор · 1×

Пример: найти, через сколько минут сгниют все апельсины в RFF. / F.FF / FF.R.

01230120FFFFFFF0очередьначало слева(0, 0)(2, 3)
свежий апельсин, Fсгнил на этой минуте, в очередитекущая клеткасосед, который гниётгнилой, готовпустая клетка

Оба гнилых апельсина, (0, 0) и (2, 3), сразу кладём в очередь: оба начинают с минуты 0

01/53
сначала · назад · пуск · шаг
Скорость
1function orangesRotting(grid):
2 queue = every rotten cell
3 fresh = number of fresh cells
4 minutes = 0
5 while queue is not empty and fresh > 0:
6 repeat queue.size times:
7 (r, c) = queue.popFront()
8 for each fresh neighbour (nr, nc):
9 grid[nr][nc] = rotten
10 fresh = fresh - 1
11 queue.pushBack((nr, nc))
12 minutes = minutes + 1
13 if fresh > 0:
14 return -1
15 return minutes
состояние
queue
[(0, 0), (2, 3)]
fresh
–
minutes
–
r
–
c
–
nr
–
nc
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Все гнилые апельсины сразу лежат в очереди, поэтому волны расходятся от каждого из них с одной скоростью.
  2. Круг берёт ровно те клетки, что лежали в очереди в его начале: они сгнили в прошлую минуту, поэтому один круг — одна минута.
  3. Каждый свежий апельсин вычитаем один раз, когда он впервые гниёт. Когда fresh стал 0, цикл останавливается; если раньше опустела очередь, какой-то апельсин отрезан и ответ -1.

Сложность

Время O(rows · cols): каждая клетка попадает в очередь не больше одного раза и проверяет четырёх соседей. Память O(rows · cols) на очередь.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.