Задача. Гнилые мандарины

Задача. На прямоугольном поддоне разложены мандарины в один слой. Также известно, что каждый день любой свежий мандарин, примыкающий к испорченному мандарину в одном из 4х направлениях (сверху, снизу, справа, слева), тоже портится.

Необходимо посчитать минимальное кол-во дней, которое должно пройти до тех пор, пока на поддоне не останется свежих мандаринов. Если такой исход невозможен, то верните -1.

Входные данные: grid - матрица размера NxM, элементы матрицы - это 3 возможных значения:

• 0 - пустая ячейка в поддоне
• 1 - свежий мандарин
• 2 - испорченный мандарин

N,M - целые числа в диапазоне от 1 до 10.

Вывод: кол-во дней, ктр должны пройти, чтобы не осталось свежих мандаринов. Если это невозможно, то -1.

1й пример

[2,1,1],
[1,1,0],
[0,1,1]

Output: 4

Пояснение:
Начальная позиция:
[2,1,1],
[1,1,0],
[0,1,1]

1 день:
[2,2,1],
[2,1,0],
[0,1,1]

2 день:
[2,2,2],
[2,2,0],
[0,1,1]

3 день:
[2,2,2],
[2,2,0],
[0,2,1]

4 день:
[2,2,2],
[2,2,0],
[0,2,2]

2й пример
[2,1,1],
[0,1,1],
[1,0,1]

Output: -1

Пояснение:
Начальная позиция:
[2,1,1],
[0,1,1],
[1,0,1]

1 день:
[2,2,1],
[0,1,1],
[1,0,1]

2 день:
[2,2,2],
[0,2,1],
[1,0,1]

3 день:
[2,2,2],
[0,2,2],
[1,0,1]

4 день, 5 день, ...:
[2,2,2],
[0,2,2],
[1,0,2]

Разбор

Для решения этой задачи достаточно просто смоделировать весь процесс. Для этой цели воспользуемся методом поиска в ширину (BFS).

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

Основной алгоритм BFS построен на цикле, проходящем по очереди. На каждой итерации мы извлекаем элемент из очереди. Затем мы выполняем некоторый процесс с всплывающим элементом. Также мы добавляем в очередь других подходящих кандидатов.

Алгоритм

1. Инициализуем начальное состояние: посчитаем кол-во свежим мандаринов, а также определим координаты испорченных мандаринов и добавим их в очередь.
2. Далее в цикле проверим все элементы очереди: для каждого элемента очереди проверим всех соседей (сверху, снизу, слева и справа). Если такие есть, добавим их в другую очередь - это мандарины, которые испортятся на след.день и мы будем использовать их на следующей итерации процесса.
3. Когда мы прошли все элементы текущей очереди, мы смоделировали 1 день процесса. Далее перейдем к просмотру элементов другой очереди.
4. В конце мы проверим, остались ли свежие мандарины. Если их нет, вернем кол-во дней, которые мы смогли смоделировать.

Реализация

Потестить код можно тут

https://dotnetfiddle.net/hpJ4Ge