Количество островов

Средняя

medium , matrix

19 October 2023

Описание задачи #

Дана матрица размером m * n, которая представляет собой карту. Каждая ячейка матрицы может принимать следующие значения:

1 — суша
0 — вода

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

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

Ограничения #

m == grid.length
n == grid[i].length
1 <= m, n <= 300
Допустимые значения в матрице — 0 или 1

Примеры #

Входные данные

[
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"],
]

Ответ: 1

Входные данные

[
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"],
]

Ответ: 3

Решение #

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

Первым делом создадим счетчик для подсчета количества островов, который будет иметь начальное значение равное 0. Далее для подсчета необходимо перебрать все элементы матрицы и выполнить следующие проверки:

если значение элемента равно 0, то мы просто его пропускаем;
если значение равно 1, то мы засчитываем попадание в остров, прибавляем единицу к счетчику и рекурсивно удаляем остров из матрицы.

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

package number_of_islands

func numIslands(grid [][]byte) int {
	counter := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] == '1' {
				counter++
				deepScan(grid, i, j)
			}
		}
	}

	return counter
}

func deepScan(grid [][]byte, i, j int) {
	grid[i][j] = '0'
	if j < len(grid[i])-1 && grid[i][j+1] == '1' {
		deepScan(grid, i, j+1)
	}
	if i < len(grid)-1 && grid[i+1][j] == '1' {
		deepScan(grid, i+1, j)
	}
	if j > 0 && grid[i][j-1] == '1' {
		deepScan(grid, i, j-1)
	}
	if i > 0 && grid[i-1][j] == '1' {
		deepScan(grid, i-1, j)
	}
}

export const numIslands = (grid: string[][]): number => {
    let counter = 0

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] == '1') {
                counter++
                deepScan(grid, i, j)
            }
        }
    }

    return counter
}

export const deepScan = (grid: string[][], i: number, j: number): void => {
    grid[i][j] = '0'

    if (j < grid[i].length - 1 && grid[i][j + 1] == '1') {
        deepScan(grid, i, j + 1)
    }
    if (i < grid.length - 1 && grid[i + 1][j] == '1') {
        deepScan(grid, i + 1, j)
    }
    if (j > 0 && grid[i][j - 1] == '1') {
        deepScan(grid, i, j - 1)
    }
    if (i > 0 && grid[i - 1][j] == '1') {
        deepScan(grid, i - 1, j)
    }
}

Оценка сложности #

По времени

Так как мы перебираем всю матрицу, то сложность перебора будет равна O(m * n). Также дополнительно может вызываться очистка острова, которая в худшем случае может занять O(m * n) операций (если вся матрица занята единицами.). Таким образом суммарная сложность O(2(m * n)), которая упрощается до O(m * n).

По памяти

O(1) — константная, так как мы выделяем дополнительную память только для хранения счетчиков.

Оригинал задачи на Leetcode

Algorithmics