Rotting Oranges

+10

Вам дана сетка в виде списка строк одинаковой длины. Каждая ячейка содержит 0 (пустая), 1 (свежий апельсин) или 2 (гнилой апельсин). Каждую минуту каждый свежий апельсин, который находится рядом с гнилым апельсином по стороне — сверху, снизу, слева или справа, — становится гнилым. Верните количество минут до тех пор, пока не останется свежих апельсинов, или -1, если какой-либо свежий апельсин никогда не сгниёт. Для сетки без свежих апельсинов в начале требуется 0 минут.

Функция

orangesRotting(grid: integer-2d-array) → integer

gridinteger-2d-array: сетка, один список из 0, 1 и 2 для каждой строки
Возвращаетinteger: Количество минут до момента, когда не останется свежих апельсинов, или -1, если этого никогда не произойдёт

Ограничения

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Каждая строка имеет одинаковую длину.
Каждый grid[i][j] — это 0, 1 или 2.

Примеры

Ввод: grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
Вывод: 6
Пояснение: Если записывать ячейки как (строка, столбец), гниение начинается с (0,0) и распространяется по единственному пути: (0,1) на 1-й минуте, (0,2) и (1,1) на 2-й минуте, (2,1) на 3-й минуте, (2,0) и (2,2) на 4-й минуте, (2,3) на 5-й минуте. Апельсин в ячейке (1,3) соприкасается только с (2,3), поэтому он испортится последним, на 6-й минуте.

Дополнительный вопрос

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

Решение

Гниение начинается одновременно от каждого гнилого апельсина и распространяется на одну ячейку в минуту, поэтому ответом будет расстояние: сколько шагов отделяет самый дальний свежий апельсин от ближайшего к нему гнилого апельсина. Именно это измеряет поиск в ширину, если перед началом поместить в очередь все гнилые апельсины и обрабатывать очередь по одному уровню за раз, по одной минуте.

Симуляция поминутно

Верно, но не успевает на самых больших тестах

Идея

Следуй тому, что описано в условии. Каждую минуту просматривай всю сетку и перечисляй все свежие апельсины, которые соприкасаются с гнилым. Затем порти их все, прибавляй единицу к счётчику времени и выполняй просмотр снова. Остановись, когда просмотр не найдёт ни одного апельсина, который можно испортить. Если к этому моменту в сетке всё ещё остался свежий апельсин, гниль до него уже никогда не доберётся: верни -1.

Сначала составь список, потом порть. Если испортить апельсин прямо во время просмотра, то клетка, проверяемая позже в том же просмотре, увидит его гнилым и тоже испортится, поэтому гниль распространится на несколько клеток за одну минуту, а счётчик времени покажет слишком маленькое значение.

Это решение верное, но каждая минута требует полного просмотра rows × cols клеток, а число минут может быть близко к числу клеток. На сетке размером 150 × 150, где свежие апельсины образуют извилистый путь, а гниль находится в его начале, на распространение гнили потребуется 11,324 минуты: 11,324 просмотра по 22,500 клеток, то есть около 2.5 × 10^8 проверок клеток, почти все из которых приходятся на клетки, которые не могут измениться.

Алгоритм

Установи минуты в 0.
Просканируй сетку и перечисли каждый свежий апельсин, у которого есть гнилой сосед.
Если список пуст, остановись. Иначе преврати каждый апельсин из списка в гнилой, прибавь 1 к минутам и просканируй сетку снова.
Верни -1, если остался свежий апельсин, иначе верни минуты.

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    minutes = 0
    while True:
        # Find every fresh orange that touches a rotten one right now.
        to_rot = []
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 2:
                        to_rot.append((r, c))
                        break
        if not to_rot:
            break
        # Rot them only after the scan, so the rot moves one step a minute.
        for r, c in to_rot:
            grid[r][c] = 2
        minutes += 1
    for row in grid:
        if 1 in row:
            return -1
    return minutes

Многоисточниковый BFS по уровням

Идея

Обход тратит время на клетки, далёкие от процесса. На минуте t+1 сгнить могут только свежие апельсины, соседние с апельсинами, которые сгнили на минуте t. Поэтому храни в очереди только их: границу гниения.

Вначале добавь в очередь все апельсины, которые сгнили на минуте 0, одновременно. Это и есть часть с несколькими источниками. Свежий апельсин сгнивает через столько минут, каково расстояние до ближайшего сгнившего апельсина, а поиск в ширину, начатый одновременно от всех источников, впервые достигает каждой клетки от ближайшего источника. Один поиск выполняет работу, для которой иначе понадобился бы отдельный поиск от каждого источника, а затем поиск минимума.

Затем обрабатывай уровни. В начале минуты в очереди находятся k апельсинов — те, что сгнили в прошлую минуту. Извлеки ровно k элементов из начала очереди; для каждого сгнои его свежих соседей и добавь их в конец. Когда все k обработаны, проходит одна минута, и в очереди находится следующая граница. В первом примере уровни такие: {(0,0)}, {(0,1)}, {(0,2), (1,1)}, {(2,1)}, {(2,0), (2,2)}, {(2,3)}, {(1,3)}: шесть шагов после начала, значит, шесть минут.

Подсчитай количество свежих апельсинов один раз в начале и уменьшай счётчик каждый раз, когда один из них сгнивает. Остановись, как только счётчик достигнет 0, иначе последний уровень добавит минуту, за которую ничего не сгниёт; если очередь опустеет, пока счётчик больше 0, верни -1. Каждая клетка попадает в очередь не более одного раза и проверяет четыре соседние клетки, поэтому объём работы равен O(rows × cols).

Алгоритм

Помести каждый гнилой апельсин в очередь и посчитай свежие.
Установи minutes равным 0. Пока очередь не пуста и остаются свежие апельсины, прибавляй 1 к minutes и запоминай размер очереди k.
Возьми k апельсинов из начала очереди. Для каждого свежего соседа внутри сетки пометь его как гнилой, уменьши количество свежих апельсинов и добавь его в конец очереди.
Когда цикл завершится, верни minutes, если количество свежих апельсинов равно 0, иначе — -1.

from collections import deque


def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Every orange that is rotten at minute 0 starts in the queue.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        minutes += 1
        # The queue holds exactly the oranges that went rotten last minute.
        # Rot their fresh neighbours; those become the next minute's queue.
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

Ловушки и крайние случаи

Большинство неверных ответов здесь отличаются на одну минуту или связаны с тем, что поиск начинается не там.

Добавление минуты за последний уровень. Если цикл выполняется, пока очередь не опустеет, на последнем проходе ничего не гниёт, но к результату всё равно добавляется 1. Останавливайтесь, как только не останется свежих апельсинов.
Поиск по очереди от каждого гнилого апельсина. При первом поиске все достигнутые апельсины учитываются по его собственным часам, поэтому время для двух источников, которые должны встретиться посередине, получается слишком большим: [[2, 1, 1, 1, 1, 1, 1, 2]] занимает 3 минуты, а не 6.
Порча апельсинов во время сканирования в варианте с пошаговым подсчётом минут. Тогда ячейка, которая будет обработана позже в том же проходе, уже увидит их гнилыми, и порча за одну минуту распространится через несколько ячеек.
Возврат -1, если нет гнилых апельсинов. Если нет и свежих апельсинов, ничего не должно происходить: [[0]] возвращает 0. Ответ -1 получается только в том случае, если свежие апельсины так и не сгнили.
Пометка апельсина как гнилого при извлечении из очереди, а не при добавлении в неё. Тогда апельсин, соседствующий с двумя гнилыми, попадёт в очередь дважды, и количество свежих апельсинов станет отрицательным.
Поиск в глубину. Он проходит по одному пути настолько глубоко, насколько возможно, поэтому то, что он первым достигает апельсина, ничего не говорит о том, через сколько минут тот сгниёт.

Частые вопросы3

Какова временная сложность задачи «Гниющие апельсины»?

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

Почему для задачи «Гниющие апельсины» используют BFS, а не DFS?

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

Что такое BFS с несколькими источниками?

Поиск в ширину, который начинается сразу с нескольких ячеек в очереди на расстоянии 0, а не с одной. За один проход он определяет расстояние от каждой ячейки до ближайшего источника — результат такой же, как при отдельном поиске для каждого источника с выбором минимального расстояния, но стоимостью одного поиска. Для любых задач на сетке, где требуется найти «расстояние до ближайшего X», используется этот алгоритм.

def orangesRotting(grid):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]

Ожидаемый вывод