rotting-oranges.md

Rotting Oranges

Jul 27, 2020 · 4 min read

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

• 0 значит пустая клетка
• 1 значит свежий апельсин
• 2 значит испорченный апельсин

Каждую минуту свежие апельсины, находящие в непосредственной близости (по 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! 🤗

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