Это самый первый вызов в рамках Saturday Coding Challenge от Hitesh Choudhary.

Ссылка на видео вышеуказанного вызова https://www.youtube.com/watch?v=a4Py6rrf2Dk

Объяснение проблемы: -

Двумерный массив (матрица) потенциально неравной высоты и ширины, содержащий только 0 и 1. Здесь 1 представляет собой шоколадные чипсы, а 0 - не шоколадные чипсы.

Задача состоит в том, чтобы найти количество шоколадных чипсов в заданной матрице.

Чоко фишка состоит из любого количества единиц, которые смежны по горизонтали или вертикали (но не по диагонали). Количество соседних единиц, образующих линию, определяет размер шоколадной фишки.

Напишите функцию, которая возвращает массив размеров всех различных шоколадных чипсов, присутствующих во входной матрице.

Что следует помнить: -

  1. Если 1 уже засчитана в шоколадной фишке, она не может считаться снова, как показано красной линией на изображении выше.
  2. Диагональные элементы не считаются смежными, как показано красной линией на изображении выше.

Примечание: -

Шоколадные чипсы для вышеуказанной задачи (изображение) обозначены зелеными линиями, а массив, содержащий решение, написан зеленым цветом.

Подход к решению: -

Две основные части решения:

  1. Чтобы отслеживать элемент, посещается он или нет.
  2. Рекурсивный поиск соседей элемента и соседей его соседей.

Простые шаги решения:

  1. Выберите элемент, отметьте его как посещенный и добавьте новый шоколадный чип в массив результатов размером 1. Найдите всех соседей элемента.

2. Если значение соседнего элемента равно 1 и он не был посещен, отметьте его посещенным и увеличьте размер шоколадного чипа. И найти всех соседей нынешнего соседа.

3. Сделайте то же, что и шаг №. 2 для всех соседей выбранного элемента, а также для всех соседей его соседей.

4. Повторите шаг №. 2 и 3, пока все соседи элемента не станут уже или их значение не станет равным 0.

5. Повторите, начиная с шага №. 1 до тех пор, пока не будут посещены все элементы матрицы.

Код решения и объяснение: -

Вот ссылка на код решения и объяснение.



Подпишись на меня в Твиттере



Спасибо Hitesh Choudhary