Ранее мы разбирали алгоритмическую задачу про острова в заданиях с собеседований для программистов. К существующему решению мы получили замечание от нашего пользователя и решили разобраться в сложности алгоритма подробнее.
Давайте проанализируем выбранный нами вариант и рассмотрим тот, который предложил пользователь Типичного Программиста.
Условие
Для двумерного массива M x N, состоящего из единиц, которые обозначают сушу, и нулей, обозначающих воду, верните количество островов.
Остров окружён водой и образован соединением соседних земель по горизонтали и вертикали. Вы можете предположить, что все четыре края матрицы окружены водой.
Примечание Если островов нет, возвращаем 0. Помечаем острова через 1, а воду обозначаем как 0.
Решение алгоритмической задачи про острова
Поиск в глубину — классический подход в решении подобных задач. Его суть заключается в том, что мы проходим по карте и для каждой 1 запускаем поиск в глубину, чтобы осмотреться вправо, влево, вверх и вниз. При каждом запуске поиска в глубину для корневого узла будем увеличивать счётчик с количеством островов.
Другими словами
Для начала нам нужно найти в матрице хотя бы одну единицу: начинаем построчный обход с нулевого индекса [0,0]. Когда мы находим единицу, помечаем её, как просмотренную, и также просматриваем соседние клетки по направлениям вправо, вниз, влево, вверх.
Если предыдущая ячейка была сушей, а следующая оказалась водой, мы возвращаемся к суше и просматриваем ячейки по перечисленным направлением в том же порядке.
Программный код
Напишем код на Java, используя три метода. Включая main, у нас также будет метод обхода острова, чтобы понять, что находится вокруг (есть ли там ещё земля или только вода), а также метод подсчёта островов, в котором и будет запускаться метод обхода.
Никаких дополнительных инструментов для реализации не нужно. В main пишем статичное расположение островов, но при желании можно поиграться с рандомной подстановкой 0 и 1.
public class Main {
public static void main(String[] args) {
//формируем расположение островов:
var map = new char[][]{
new char[]{'1','1','0','0','0'},
new char[]{'1','1','0','0','0'},
new char[]{'0','0','1','0','0'},
new char[]{'0','0','0','1','0'}
};
System.out.println("Количество островов: " + howMuchlands(map));
}
//метод обхода острова, который принимает матрицу и координаты:
private static void markIsland(char[][] matrix, int x, int y) {
int xLength = matrix.length;
int yLength = matrix[0].length;
//условие выхода за край матрицы:
if (x < 0 || y < 0 || x >= xLength || y >= yLength || matrix[x][y] == '0') {
return;
}
//если не вышли за границу, помечаем ячейку как 0:
matrix[x][y] = '0';
//осматриваемся:
markIsland(matrix, x - 1, y); //вверх
markIsland(matrix, x + 1, y); //вниз
markIsland(matrix, x, y - 1); //влево
markIsland(matrix, x, y + 1); //вправо
}
//метод расчёта:
public static int howMuchlands(char[][] matrix) {
int xLength = matrix.length;
if (xLength == 0) return 0;
int yLength = matrix[0].length;
//переменная, хранящая кол-во островов:
int numIslands = 0;
//перебор строк:
for (int i = 0; i < xLength; i++) {
//перебор столбцов:
for (int j = 0; j < yLength; j++) {
if (matrix[i][j] == '1') {
//если находим "1", то увеличиваем каунтер островов:
numIslands++;
//запускаем метод обхода острова по периметру:
markIsland(matrix, i, j);
}
}
}
return numIslands;
}
}Проверяем решение
В случае с нашей картой и с учётом того, что по диагонали острова не соединяются, мы должны получить в результате три острова, что и видим на выходе программы:
Здесь вы можете запустить аналгичную программу на C#, а также изменить шаблон карты по своему усмотрению.
Сложность алгоритма
Сложность решения алгоритмической задачи про острова — O(m*n), где m — количество строк, а n — количество столбцов нашей матрицы.
Решение от пользователя
Есть вариант более быстрого решения, при котором программа не затормозит в случае большого массива данных:
А с каким решением согласны вы? Может, у вас есть своё? Предложите альтернативную реализацию в комментариях.
