Определение количества островов на карте озера

RU | EN | FR | JP | DE | CH | KR

Описание

Дана карта озера в виде двумерного массива, где каждая ячейка представляет собой либо воду ('W'), либо сушу ('L'). Задача состоит в определении количества отдельных островов на этой карте. Остров определяется как группа смежных (соединённых по вертикали или горизонтали) ячеек суши, окруженных водой.

Пример

Пример карты озера:

[ ['W', 'L', 'W', 'W'], ['W', 'L', 'L', 'W'], ['W', 'W', 'L', 'W'], ['L', 'W', 'W', 'L'] ]

Ожидаемый результат: На карте присутствуют 3 отдельных острова. Один остров состоит из двух смежных ячеек 'L' во втором столбце, второй — из одной ячейки в третьей строке, третьей колонке, и третий — из двух недиагонально смежных ячеек в последней строке.

Задачи

1. Разработать алгоритм, использующий поиск в ширину (BFS), для определения количества островов на карте.
2. Визуализировать процесс поиска, отмечая посещенные и проверенные ячейки.
3. Посчитать количество выполненных шагов (перемещений) в процессе поиска.

Алгоритм

1. Инициализируем счетчик островов и пустую очередь для BFS.
2. Проходим по каждой ячейке карты.
3. Если текущая ячейка - суша и ее еще не посещали, то запускаем BFS для поиска острова.
4. В процессе BFS отмечаем посещенные ячейки и увеличиваем счетчик шагов.
5. BFS заканчивается, когда мы обходим все смежные ячейки данного острова.
6. Повторяем шаги 3-5 для всех ячеек на карте.

Визуализация

В процессе выполнения алгоритма мы будем визуализировать посещенные и проверенные ячейки. Это поможет наглядно представить процесс поиска островов на карте.

Результат

После завершения алгоритма мы получим количество отдельных островов на карте озера и количество выполненных шагов (перемещений) в процессе поиска.

Лицензия

Этот проект лицензируется по лицензии MIT - подробности см. в файле LICENSE.