200. Number of Islands

Level - medium

Task

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Объяснение

Задача (Количество островов) заключается в определении количества отдельных островов на двумерной сетке, представленной в виде матрицы. Каждая ячейка матрицы может быть либо землей ('1'), либо водой ('0'). Островом считается группа соединенных по вертикали или горизонтали ячеек, занятых землей.

Вот основные шаги для решения этой задачи:

1. Инициализация Начните с инициализации счетчика островов.

2. Проход по матрице Проходим по каждой ячейке матрицы. Если ячейка содержит землю ('1'), увеличьте счетчик островов и запустите процедуру поиска, чтобы пометить все соединенные ячейки земли как посещенные.

3. Поиск и маркировка: Используйте поиск в глубину (DFS) или поиск в ширину (BFS) для маркировки всех соединенных ячеек земли. Это гарантирует, что все ячейки одного острова будут помечены и не будут учтены повторно.

4. Возвращение результата После прохода по всей матрице верните значение счетчика островов.

Пример матрицы и её интерпретация:

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

В этом примере есть три острова:

1. Один остров в верхнем левом углу, состоящий из шести ячеек земли.
2. Один остров в третьей строке, состоящий из одной ячейки земли.
3. Один остров в нижнем правом углу, состоящий из двух ячеек земли.

Таким образом, решением этой задачи будет число 3.

Example 1:

Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.