Код Senior Графы: BFS и DFS обновлено
Распространение по слоям
Условие
Матрица: 0 - пусто, 1 - свежий, 2 - гнилой. Каждую минуту гниль переходит на соседей по четырём сторонам. Сколько минут до полного загнивания? Если есть недостижимые свежие - -1.
Примеры
orangesRotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]) // 4
orangesRotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]) // -1
orangesRotting([[0, 2]]) // 0
Как подойти
BFS из нескольких источников одновременно - приём, который не приходит в голову сразу: кладём в очередь все стартовые клетки и обрабатываем слоями. Счётчик оставшихся свежих избавляет от второго прохода по матрице в конце и заодно даёт условие остановки.
Подсказки: 3
- Начальная очередь - сразу все гнилые: это BFS из нескольких источников.
- Считай минуты по слоям, а не по отдельным клеткам.
- Оставшиеся свежие означают, что до них не добраться.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.