How many islands
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
function numIslands(grid) {
if (!grid || grid.length === 0) {
return 0;
}
let islandCount = 0;
const rows = grid.length;
const cols = grid[0].length;
// Рекурсивная функция для "затопления" острова (DFS)
function dfs(r, c) {
// Базовый случай: проверка границ матрицы и проверка на воду ('0')
if (r < 0 || c < 0 || r >= rows || c >= cols || !grid[r][c]) {
return;
}
// "Затапливаем" текущую ячейку, чтобы не возвращаться к ней
grid[r][c] = 0;
// Рекурсивно обходим всех соседей (вверх, вниз, влево, вправо)
dfs(r - 1, c); // вверх
dfs(r + 1, c); // вниз
dfs(r, c - 1); // влево
dfs(r, c + 1); // вправо
}
// Основной цикл обхода всей сетки
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
// Если нашли сушу, нашли новый остров
if (grid[r][c] === 1) {
islandCount++;
// Запускаем DFS, чтобы стереть весь этот остров из матрицы
dfs(r, c);
}
}
}
return islandCount;
}
// Пример матрицы с картинки
const matrix = [
[1, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 1, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 0]
];
console.log("Количество островов:", numIslands(matrix)); // Выведет: 3
JavaScript
INFO