В продолжение нашей практики проверки кода мы будем решать общую проблему под названием «Число островов», используя технику обхода графа под названием «Поиск в глубину» (DFS, в дальнейшем).

Настройка проблемы:

У нас есть сетка m x n, представленная вложенным массивом выше. 1 обозначают участки суши, а 0 - океан. Под землей считается 1, которые примыкают по горизонтали или вертикали, но не по диагонали. Учитывая сетку, подобную приведенной выше, верните количество островов.

Подход DFS:

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

Мы будем сканировать график слева направо, сверху вниз, и каждый раз, когда мы достигаем значения 1, мы запускаем функцию DFS. Эта функция изменит значение текущего узла на 0, чтобы пометить его как посещенный. Функция также будет рекурсивно проверять горизонтальных и вертикальных соседей. Перед тем, как запустить функцию, мы увеличиваем переменную счетчика, поскольку DFS удалит всю сушу, прежде чем сканирование переместится через оставшуюся часть графика.

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

Я думаю, что ключевым моментом в решении этой проблемы является понимание нашей функции DFS. В проблеме конкретно указаны вертикальные и горизонтальные соседи. Итак, в нашей функции DFS мы сделаем 3 основных шага:

  • Определите базовый вариант, чтобы выйти из нашего рекурсивного подхода
  • Требуемая «работа», в данном случае преобразование «1» в «0»
  • Выполнение 4 рекурсивных вызовов функций в 4 смежных направлениях.

Функция DFS:

Я объявил несколько переменных, острова в качестве своего счетчика вместе с maxRows и maxColumns. Эти переменные используются для определения границ графа. Если мы разбиваем основу нашей функции DFS, это в основном гарантирует, что наша функция не выполняет поиск за пределами границ и что конкретный узел, на который мы смотрим, является сушей, в противном случае мы завершаем рекурсивный вызов .

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

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

Итерации по 2D-массиву:

Теперь, когда у нас есть функция DFS, мы просто перебираем массив, и если мы встречаем значение узла, равное 1, мы увеличиваем счетчик островов и активируем функцию DFS для преобразования всей суши в плитки океана.

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

Заключение:

Я столкнулся с этой проблемой и хотел поделиться решением, к которому пришел, потому что сначала эту проблему сложно переварить. Вы должны осознать, что это проблема обхода графа, DFS или BFS (поиск в ширину) являются жизнеспособными методами обхода для этой проблемы. Затем вы должны логически подумать о том, как вы хотите настроить рекурсивную функцию и каким должен быть базовый случай. Приходя к осознанию того, что все, что вы делаете, это подсчет экземпляров, в которых вы вызываете свою функцию DFS, является кульминацией всех этих более мелких проблем.

Этот ресурс от Visualgo отлично подходит, если вы хотите визуализировать обход графа и хотите освежить в памяти концепции DFS / BFS.

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