1. Идея

В задаче дана прямоугольная таблица:

• 0 — пустая клетка,
• 1 — свежий апельсин,
• 2 — гнилой апельсин.

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

Нужно найти минимальное число минут, за которое сгниют все апельсины. Если это невозможно, ответ -1.

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

Значит, нужно сделать мультистартовый BFS:

• в очередь сразу положить все клетки с 2,
• затем волнами распространять гниль на соседние клетки с 1,
• номер волны и будет временем в минутах.

2. Наблюдения

Наблюдение 1. Все гнилые апельсины действуют одновременно

Если в начале есть несколько гнилых апельсинов, нельзя запускать BFS отдельно от каждого — это даст неправильное время.
Нужно считать, что все они начинают заражение в один и тот же момент.

Именно поэтому все клетки со значением 2 сразу добавляются в очередь.

Наблюдение 2. BFS естественно считает минимальное время

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

Почему так:

• сначала обрабатываются клетки, которые уже гнилые в момент 0,
• потом клетки, сгнившие через 1 минуту,
• потом через 2 минуты,
• и так далее.

Это и есть стандартное свойство BFS: он идёт по расстояниям слоями.

Наблюдение 3. Нужно отдельно считать количество свежих апельсинов

Если свежих апельсинов нет изначально, ответ сразу 0.

Во время BFS удобно уменьшать счётчик свежих апельсинов каждый раз, когда очередной свежий становится гнилым.
Тогда в конце:

• если счётчик стал 0, все апельсины сгнили;
• если нет, часть апельсинов была недостижима, значит ответ -1.

Наблюдение 4. Недостижимые клетки остаются свежими навсегда

Например, если свежий апельсин отделён пустыми клетками и рядом нет пути распространения гнили, он никогда не сгниёт.

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

3. Алгоритм

Пусть таблица имеет размеры n x m.

1. Пройти по всей таблице.
2. Для каждой клетки:
   • если там 2, добавить её координаты в очередь;
   • если там 1, увеличить счётчик свежих апельсинов.
3. Если свежих апельсинов нет, вернуть 0.
4. Запустить BFS из всех гнилых апельсинов одновременно.
5. Пока очередь не пуста:
   • взять клетку из очереди вместе с временем, когда она стала гнилой;
   • посмотреть 4 соседние клетки;
   • если сосед находится внутри таблицы и содержит 1, то:
     • сделать его гнилым (2);
     • уменьшить число свежих апельсинов;
     • добавить соседа в очередь с временем time + 1;
     • обновить ответ.
6. После BFS:
   • если свежие апельсины ещё остались, вернуть -1;
   • иначе вернуть максимальное время, до которого дошёл BFS.

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

Докажем корректность алгоритма.

1. Все возможные заражения учитываются

В очередь изначально помещаются все гнилые апельсины.
Значит, BFS стартует одновременно из всех источников гнили.

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

2. Время заражения каждой клетки найдено минимально

BFS обрабатывает клетки по неубыванию времени:

• сначала все клетки времени 0,
• затем времени 1,
• затем времени 2 и так далее.

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

Следовательно, время, записанное для клетки, минимально возможное.

3. Максимальное из этих времён — ответ задачи

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

Именно это значение алгоритм сохраняет в переменной ответа.

4. Если после BFS остались свежие апельсины, ответ -1

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

Поэтому в этом случае правильный ответ — -1.

Из пунктов 1–4 следует, что алгоритм всегда возвращает правильный ответ.

5. Сложность

Пусть n — число строк, m — число столбцов.

Время

Каждая клетка:

• один раз просматривается при начальном обходе,
• не более одного раза добавляется в очередь в BFS.

Значит, общая сложность:

O(n * m)

Память

В худшем случае в очереди может оказаться до n * m клеток.

Итого:

O(n * m)

CPP

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int n = (int)grid.size();
        int m = (int)grid[0].size();

        queue<pair<int, int>> q;
        int fresh = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 2) {
                    q.push({i, j});
                } else if (grid[i][j] == 1) {
                    ++fresh;
                }
            }
        }

        if (fresh == 0) return 0;

        int minutes = 0;
        const int dx[4] = {-1, 1, 0, 0};
        const int dy[4] = {0, 0, -1, 1};

        while (!q.empty()) {
            int sz = (int)q.size();
            bool changed = false;

            for (int k = 0; k < sz; ++k) {
                auto [x, y] = q.front();
                q.pop();

                for (int dir = 0; dir < 4; ++dir) {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];

                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if (grid[nx][ny] != 1) continue;

                    grid[nx][ny] = 2;
                    --fresh;
                    q.push({nx, ny});
                    changed = true;
                }
            }

            if (changed) ++minutes;
        }

        return fresh == 0 ? minutes : -1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

    Solution solution;
    cout << solution.orangesRotting(grid) << '\n';

    return 0;
}

PYTHON

from collections import deque
import sys


class Solution:
    def orangesRotting(self, grid):
        n = len(grid)
        m = len(grid[0])

        q = deque()
        fresh = 0

        for i in range(n):
            for j in range(m):
                if grid[i][j] == 2:
                    q.append((i, j))
                elif grid[i][j] == 1:
                    fresh += 1

        if fresh == 0:
            return 0

        minutes = 0
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while q:
            sz = len(q)
            changed = False

            for _ in range(sz):
                x, y = q.popleft()

                for dx, dy in directions:
                    nx, ny = x + dx, y + dy

                    if nx < 0 or nx >= n or ny < 0 or ny >= m:
                        continue
                    if grid[nx][ny] != 1:
                        continue

                    grid[nx][ny] = 2
                    fresh -= 1
                    q.append((nx, ny))
                    changed = True

            if changed:
                minutes += 1

        return minutes if fresh == 0 else -1


def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return

    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    grid = [[int(next(it)) for _ in range(m)] for _ in range(n)]

    solution = Solution()
    print(solution.orangesRotting(grid))


if __name__ == "__main__":
    main()