1. Идея

Нужно найти максимальную площадь острова в двумерной сетке.

Островом считается связная по сторонам группа клеток со значением 1. Клетки со значением 0 — это вода. Требуется определить, сколько клеток содержит самый большой остров.

Главная идея очень стандартная для задач на сетки:
перебираем все клетки поля, и если находим ещё не посещённую клетку суши (1), то запускаем обход всего её острова. Размер этого острова считаем и обновляем ответ.

Для обхода подойдёт либо DFS (поиск в глубину), либо BFS (поиск в ширину). В этой задаче удобно использовать DFS.

2. Наблюдения

Наблюдение 1. Каждый остров можно посчитать отдельно

Если мы попали в клетку суши, то все клетки этого же острова можно достичь, двигаясь только вверх, вниз, влево и вправо по клеткам со значением 1.

Значит, достаточно один раз обойти весь остров и посчитать количество его клеток.

Наблюдение 2. Нужно избегать повторного посещения

Если не отмечать клетки как посещённые, один и тот же остров будет пересчитываться много раз.

Поэтому после посещения клетки нужно:

• либо хранить отдельный массив visited,
• либо сразу менять значение в grid, например превращать 1 в 0.

Второй вариант проще и экономит память.

Наблюдение 3. Ответ — максимум среди площадей всех островов

После того как мы умеем находить площадь одного острова, остаётся:

• пройти по всем клеткам,
• для каждой новой клетки суши посчитать площадь её острова,
• поддерживать максимальное значение.

3. Алгоритм

Пусть размеры сетки — n × m.

1. Считываем grid.
2. Создаём переменную ans = 0.
3. Перебираем все клетки (i, j):
   • если grid[i][j] == 1, запускаем DFS из этой клетки;
   • DFS возвращает площадь текущего острова;
   • обновляем ans = max(ans, area).
4. Выводим ans.

Как работает DFS

Функция dfs(i, j):

1. Если клетка вне границ поля, возвращаем 0.
2. Если в клетке вода (0), возвращаем 0.
3. Иначе это суша:
   • помечаем клетку как посещённую, например grid[i][j] = 0;
   • считаем текущую клетку: 1;
   • рекурсивно идём в 4 направления:
     • вверх,
     • вниз,
     • влево,
     • вправо.
4. Возвращаем сумму: 1 + dfs(вверх) + dfs(вниз) + dfs(влево) + dfs(вправо).

4. Почему это работает

Докажем, что алгоритм действительно находит площадь максимального острова.

1. DFS считает площадь острова правильно

Рассмотрим запуск DFS из некоторой клетки суши.

• Функция посещает эту клетку и добавляет 1 к ответу.
• Затем она переходит во все соседние по стороне клетки.
• Если сосед тоже суша, DFS продолжает обход.
• Если сосед — вода или выход за границы, вклад равен 0.

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

2. Каждый остров будет посчитан ровно один раз

При первом попадании в любую клетку острова мы запускаем DFS и помечаем все клетки этого острова как посещённые.

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

Значит:

• ни один остров не пропускается;
• ни один остров не считается дважды.

3. Максимум среди всех найденных площадей — правильный ответ

Алгоритм вычисляет площадь каждого острова и берёт максимум.

По определению, максимальная площадь среди всех островов и есть ответ задачи.

Следовательно, алгоритм корректен.

5. Сложность

Пусть n — число строк, m — число столбцов.

Время

Каждая клетка:

• либо один раз проверяется во внешнем цикле,
• либо один раз обрабатывается в DFS.

Итого асимптотика:

O(n * m)

Память

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

В худшем случае весь массив состоит из единиц, и глубина рекурсии может достигать O(n * m).

Итого:

• дополнительная память: O(n * m) в худшем случае из-за рекурсии.

CPP

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = (int)grid.size();
        if (n == 0) return 0;
        int m = (int)grid[0].size();

        int answer = 0;
        const int dx[4] = {-1, 1, 0, 0};
        const int dy[4] = {0, 0, -1, 1};

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] != 1) continue;

                int area = 0;
                stack<pair<int, int>> st;
                st.push({i, j});
                grid[i][j] = 0;

                while (!st.empty()) {
                    auto [x, y] = st.top();
                    st.pop();
                    ++area;

                    for (int dir = 0; dir < 4; ++dir) {
                        int nx = x + dx[dir];
                        int ny = y + dy[dir];

                        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                        if (grid[nx][ny] != 1) continue;

                        grid[nx][ny] = 0;
                        st.push({nx, ny});
                    }
                }

                answer = max(answer, area);
            }
        }

        return answer;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

    Solution solver;
    cout << solver.maxAreaOfIsland(grid) << '\n';

    return 0;
}

PYTHON

import sys


class Solution:
    def maxAreaOfIsland(self, grid):
        n = len(grid)
        if n == 0:
            return 0
        m = len(grid[0])

        answer = 0
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        for i in range(n):
            for j in range(m):
                if grid[i][j] != 1:
                    continue

                area = 0
                stack = [(i, j)]
                grid[i][j] = 0

                while stack:
                    x, y = stack.pop()
                    area += 1

                    for dx, dy in directions:
                        nx = x + dx
                        ny = y + dy

                        if nx < 0 or nx >= n or ny < 0 or ny >= m:
                            continue
                        if grid[nx][ny] != 1:
                            continue

                        grid[nx][ny] = 0
                        stack.append((nx, ny))

                answer = max(answer, area)

        return answer


def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return

    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    grid = [[int(next(it)) for _ in range(m)] for _ in range(n)]

    solver = Solution()
    print(solver.maxAreaOfIsland(grid))


if __name__ == "__main__":
    main()