1. Идея

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

Это классическая задача на обход компонент связности в сетке. Если встретили клетку суши 1, которая ещё не была посещена, значит, начинается новый остров. Запускаем из неё обход в глубину или в ширину, отмечаем все достижимые клетки этого острова и считаем их количество. После этого обновляем ответ — максимум из всех найденных площадей.

В эталонном решении используется итеративный DFS через стек.

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

1. Остров образуют только клетки 1.
2. Связь есть только по четырём направлениям:
   • вверх
   • вниз
   • влево
   • вправо
3. Если клетка уже была посещена при обходе какого-то острова, повторно её рассматривать не нужно.
4. Каждая клетка карты попадёт в обход не более одного раза, поэтому решение будет достаточно быстрым.
5. Если на всей карте нет ни одной 1, то ответ останется равным 0.

3. Алгоритм

Пусть размеры карты — n строк и m столбцов.

1. Считываем таблицу grid.
2. Создаём массив used такого же размера, где будем хранить, посещали ли клетку.
3. Заводим переменную ans = 0.
4. Проходим по всем клеткам (i, j):
   • если grid[i][j] != 1, пропускаем;
   • если used[i][j] = true, тоже пропускаем;
   • иначе нашли новую компоненту связности, то есть новый остров.
5. Для нового острова:
   • создаём стек;
   • кладём туда клетку (i, j);
   • помечаем её посещённой;
   • запускаем цикл, пока стек не пуст:
     • достаём клетку;
     • увеличиваем текущую площадь area;
     • смотрим 4 соседей;
     • если сосед внутри границ, не посещён и равен 1, помечаем его и кладём в стек.
6. После завершения обхода этого острова обновляем ans = max(ans, area).
7. После обработки всей таблицы выводим ans.

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

Рассмотрим любую клетку суши.

• Если она ещё не посещена, то из неё начинается обход, который пойдёт только по клеткам 1, связанным по стороне.
• Значит, будут найдены все и только те клетки, которые принадлежат одному острову.
• Каждая такая клетка добавится в стек ровно один раз, потому что перед добавлением мы сразу отмечаем её как посещённую.
• Следовательно, значение area после завершения обхода равно площади ровно этого острова.

Теперь посмотрим на всю карту.

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

Мы берём максимум из площадей всех найденных островов, поэтому итоговый ans и есть площадь наибольшего острова.

5. Сложность

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

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

При ограничениях до 50 x 50 это работает мгновенно.

6. Код на C++17

#include <bits/stdc++.h>
using namespace std;

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];
        }
    }

    vector<vector<char>> used(n, vector<char>(m, 0));
    int ans = 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 || used[i][j]) continue;

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

            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 (used[nx][ny] || grid[nx][ny] != 1) continue;
                    used[nx][ny] = 1;
                    st.push({nx, ny});
                }
            }

            ans = max(ans, area);
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

import sys

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

    it = iter(data)
    n = int(next(it))
    m = int(next(it))

    grid = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            grid[i][j] = int(next(it))

    used = [[False] * m for _ in range(n)]
    ans = 0
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

            area = 0
            stack = [(i, j)]
            used[i][j] = True

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

                for dx, dy in dirs:
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < n and 0 <= ny < m and not used[nx][ny] and grid[nx][ny] == 1:
                        used[nx][ny] = True
                        stack.append((nx, ny))

            if area > ans:
                ans = area

    print(ans)

if __name__ == "__main__":
    main()