PHP-программа для нахождения количества островов | Набор 1 (с использованием DFS)

Опубликовано: 7 Октября, 2022

Учитывая логическую двумерную матрицу, найдите количество островов. Группа соединенных единиц образует остров. Например, приведенная ниже матрица содержит 5 островов.
Пример:

Input : mat[][] = {{1, 1, 0, 0, 0},
                   {0, 1, 0, 0, 1},
                   {1, 0, 0, 1, 1},
                   {0, 0, 0, 0, 0},
                   {1, 0, 1, 0, 1} 
Output : 5

Это вариация стандартной задачи: «Подсчет количества компонент связности в неориентированном графе».
Прежде чем мы перейдем к проблеме, давайте разберемся, что такое связный компонент. Компонента связности неориентированного графа — это подграф, в котором каждые две вершины соединены друг с другом путем (путями) и который не связан ни с какими другими вершинами вне подграфа.
Например, граф, показанный ниже, имеет три компоненты связности.

Пожалуйста, обратитесь к полной статье «Найти количество островов» | Установите 1 (используя DFS) для более подробной информации!

РЕКОМЕНДУЕМЫЕ СТАТЬИ