1. Идея

Нужно найти самую большую компоненту связности среди клеток со значением 1 в прямоугольной таблице.

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

Для этого удобно запускать обход в ширину BFS из каждой ещё не посещённой клетки с 1. Один запуск BFS полностью обходит один сад и считает его размер. Среди всех размеров остаётся взять максимум.

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

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

3. Алгоритм

Будем просматривать все клетки таблицы.

Для каждой клетки (i, j):

• если там стоит 0, она нас не интересует;
• если там стоит 1, но клетка уже посещена, значит этот сад уже был обработан;
• если там стоит 1 и она ещё не посещена, значит мы нашли новый сад.

Тогда:

1. создаём очередь для BFS;
2. кладём в неё стартовую клетку;
3. помечаем её как посещённую;
4. пока очередь не пуста:
   • извлекаем клетку;
   • увеличиваем размер текущего сада;
   • пробуем перейти в 4 соседние клетки;
   • если сосед находится внутри таблицы, содержит 1 и ещё не посещён, добавляем его в очередь и помечаем посещённым;
5. после завершения BFS сравниваем размер найденного сада с текущим ответом.

В конце выводим максимальный размер.

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

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

Рассмотрим любой запуск BFS из некоторой клетки с 1, которая ещё не посещена.

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

Следовательно, один запуск BFS считает размер ровно одного сада.

Почему каждый сад будет обработан ровно один раз?

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

Таким образом:

• каждый сад учитывается один раз;
• для каждого сада вычисляется его точный размер;
• среди этих размеров берётся максимум.

Значит, алгоритм корректно находит размер самого большого сада.

5. Сложность

Пусть всего в таблице n * m клеток.

• Каждая клетка просматривается во внешних циклах один раз.
• Каждая клетка может попасть в очередь BFS не более одного раза.
• Для каждой клетки проверяются 4 соседа.

Итоговая сложность по времени: O(n * m).

Память:

• таблица grid — O(n * m),
• массив used — O(n * m),
• очередь в худшем случае — до O(n * m).

Итоговая сложность по памяти: O(n * m).

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

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

    vector<vector<bool>> used(n, vector<bool>(m, false));
    int answer = 0;

    int dx[4] = {-1, 1, 0, 0};
    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]) {
                queue<pair<int, int>> q;
                q.push({i, j});
                used[i][j] = true;
                int size = 0;

                while (!q.empty()) {
                    pair<int, int> cur = q.front();
                    q.pop();
                    int x = cur.first;
                    int y = cur.second;
                    size++;

                    for (int k = 0; k < 4; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                            if (grid[nx][ny] == '1' && !used[nx][ny]) {
                                used[nx][ny] = true;
                                q.push({nx, ny});
                            }
                        }
                    }
                }

                if (size > answer) {
                    answer = size;
                }
            }
        }
    }

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

7. Код на Python 3

from collections import deque

n, m = map(int, input().split())
grid = [input().strip() for _ in range(n)]

used = [[False] * m for _ in range(n)]
answer = 0

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(n):
    for j in range(m):
        if grid[i][j] == '1' and not used[i][j]:
            q = deque()
            q.append((i, j))
            used[i][j] = True
            size = 0

            while q:
                x, y = q.popleft()
                size += 1

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

            if size > answer:
                answer = size

print(answer)