Rotting Oranges

Есть прямоугольное поле, в каждой клетке которого могут быть:

Каждую минуту свежие апельсины, находящие в непосредственной близости (по 4 осям) от испорченных, так же портятся. Найти минимальное количество минут после которых все фрукты на поле окажутся испорченными. Если это невозможно, вернуть -1.

Задача на LeetCode

Решение #

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

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

Важно как именно обходить граф. Есть два варианта — в глубины (DFS) и в ширину (BFS). Обход в глубину ещё называют рекурсивным перебором, который я уже рассматривал в задаче про домино и тримино.

Важно понять какой именно вариант подходит по смыслу в данной задаче. За одну минуту портятся соседние апельсины одновременно — это ключ к решению. Как работает поиск в ширину?

Создаём очередь. Кладём туда узлы, с которых хотим начать обход графа, в нашем случае — это уже испорченный апельсины, на момент времени ноль. Далее начинаем доставать с начала очереди узлы и смотреть на деток: кладём их так же в очередь и увеличиваем количество минут на 1 для каждой из них. В каждый момент времени в очереди лежит испорченный апельсин и количество минут через которое он испортился. Ответом будем количество минут от последнего апельсина в очереди.

После того как положили узлы в очередь надо не забывать пометить их как visited. В общем случае, можно завести set куда класть обработанные узлы. В нашем случае, для этого можно использовать то же поле, помечая там апельсины как испорченные.

Что если до каких-то свежих апельсинов, используя такой переход, нам не добраться? В таком случае просят вернуть -1. Как это укладывается в текущую модель?

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

В JavaScript очереди нет, но можно использовать массив: push добавляет в конец очереди, shift убирает с начала очереди. Важно, что с точки зрения сложности shift это не O(1), т.к. надо пересчитать индексы всех элементов — все-таки это «массив».

Обычно, в таких случаях допустимо сказать «представим, что у нас есть очередь, условно объекты типа Queue, с таким интерфейсом и сложностью операций, и представим, что он уже реализован». На собеседовании этого бывает достаточно.

Рассмотрим краевой случай. Что если изначально на поле вообще нет фруктов? Тогда должно пройти ровно 0 минут прежде чем на поле не окажется свежих фруктов. Инициализируем ответ minutesPassed нулём.

Решение есть. Напишем код.

const ROTTEN = 2;
const FRESH = 1;

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function(field) {
    const q = [];
    const h = field.length;
    const w = field[0].length;
    let fresh = 0;

    // шаг 1
    // кладём в очередь все неспелые фрукты,
    // считаем количество свежих
    for (let y = 0; y < h; y++) {
        for (let x = 0; x < w; x++) {
            if (field[y][x] === ROTTEN) {
                // в очереди будем хранить
                // координаты апельсина
                // и сколько прошло минут
                // прежде чем он испортился
                q.push([y, x, 0]);
            } else if (field[y][x] === FRESH) {
                fresh++;
            }
        }
    }

    let minutesPassed = 0;

    // шаг 2
    // поиск в ширину (BFS):
    // обходим все узлы,
    // пока очередь не опустеет
    while (q.length > 0) {
        const [y, x, clock] = q.shift();
        // правильный ответ даст
        // последний элемент в очереди,
        // но можно без лишних условий
        // обновлять minutesPassed всегда
        minutesPassed = clock;

        // рассматриваем все 4 направления,
        // возможные переходы к свежим апельсинам
        for (let [y1, x1] of [
            [y + 1, x],
            [y, x + 1],
            [y - 1, x],
            [y, x - 1]
        ]) {
            // не выходим за границы поля,
            // кладём в очередь только
            // свежие апельсины,
            // пропуская уже испорченные
            // ранее и пустые клетки
            if (
                y1 >= 0 && y1 < h && x1 >= 0 && x1 < w &&
                field[y1][x1] === FRESH
            ) {
                // кладём нужные координаты
                // и не забываем увеличить
                // количество минут на один
                q.push([y1, x1, clock + 1]);

                // не забываем отметить на поле
                // апельсин как испорченный,
                // иначе будем ходить по
                // одним и тем же путям в графе
                field[y1][x1] = ROTTEN;

                // свежих апельсинов становится меньше
                fresh--;
            }
        }
    }
    return fresh === 0 ? minutesPassed : -1;
}

PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

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