MiddleКодЧастоЕщё не отвечали
Подсчёт островов суши в сетке 0/1 заливкой
Дана прямоугольная сетка из 0 (вода) и 1 (суша). Посчитайте острова — максимальные группы клеток суши, связанных по 4 направлениям (вверх, вниз, влево, вправо).
Требования:
- Каждая клетка суши принадлежит ровно одному острову.
- Посещайте каждую клетку не более константного числа раз.
int countIslands(std::vector<std::vector<int>>& grid) {
// ваш код здесь
}Допишите реализацию.
Сканируем каждую клетку. На непосещённой клетке суши увеличиваем счётчик островов и заливаем всю её связную компоненту через DFS или BFS, помечая каждую достигнутую клетку посещённой (например, обнуляя её). Заливка стоит на воде и границах, каждая клетка посещается константно.
- ✗Считать каждую клетку суши островом вместо каждой связной компоненты
- ✗Не помечать посещённые клетки, из-за чего один остров считается повторно
- ✗Путать 4- и 8-направленную смежность, меняя ответ
- →Как 8-направленная связность изменит подсчёт?
- →Как избежать переполнения стека на огромной сетке при рекурсивном DFS?
Оглавление
Задача
Посчитайте острова суши в сетке 0/1 (связность по 4 направлениям) заливкой.
Решение
#include <vector>
static void flood(std::vector<std::vector<int>>& g, int r, int c) {
if (r < 0 || c < 0 || r >= (int)g.size() || c >= (int)g[0].size() || g[r][c] == 0)
return;
g[r][c] = 0; // пометить посещённой
flood(g, r + 1, c); flood(g, r - 1, c); // 4 направления
flood(g, r, c + 1); flood(g, r, c - 1);
}
int countIslands(std::vector<std::vector<int>>& grid) {
int count = 0;
for (int r = 0; r < (int)grid.size(); ++r)
for (int c = 0; c < (int)grid[0].size(); ++c)
if (grid[r][c] == 1) { ++count; flood(grid, r, c); }
return count;
}Ключевые моменты
- Считаем связные компоненты, а не отдельные клетки суши.
- Заливка помечает клетки, чтобы остров не считался дважды.
- Связность 4 против 8 направлений меняет ответ — уточняйте.
Оглавление
