Простая и сложная версии фактически представляют собой разные задачи, поэтому внимательно прочитайте условия обеих задач. Единственное различие между двумя версиями — это применяемая операция.
У Алекса есть матрица из \(n\) строк и \(m\) столбцов, состоящая из символов '.' и '#'. Набор '#' ячеек формирует компоненту связности, если из любой ячейки в этом наборе можно достичь любую другую ячейку в этом наборе, перемещаясь только в другую ячейку набора, которая имеет общую сторону. Размер компоненты связности — это количество ячеек в наборе.
За одну операцию Алекс выбирает любую строку \(r\) (\(1 \le r \le n\)) или любой столбец \(c\) (\(1 \le c \le m\)), затем устанавливает каждую ячейку в строке \(r\) или столбце \(c\) равной '#'. Помогите Алексу найти максимально возможный размер наибольшей компоненты связности из ячеек '#', который он может достичь после выполнения операции не более одного раза.
Выходные данные
Для каждого теста выведите одно целое число — максимально возможный размер компоненты связности из ячеек '#', который может достичь Алекс.
Примечание
Во втором примере для Алекса оптимально установить все ячейки в столбце \(2\) равными '#'. Это приведет к тому, что наибольшая компонента связности из '#' будет иметь размер \(6\).
В третьем примере для Алекса оптимально установить все ячейки в строке \(2\) равными '#'. Это приведет к тому, что наибольшая компонента связности из '#' будет иметь размер \(9\).
В четвертом примере для Алекса оптимально установить все ячейки в строке \(4\) равными '#'. Это приведет к тому, что наибольшая компонента связности из '#' будет иметь размер \(11\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 1
.
4 2
..
#.
#.
.#
3 5
.#.#.
..#..
.#.#.
5 5
#...#
....#
#...#
.....
...##
6 6
.#..#.
#..#..
.#...#
#.#.#.
.#.##.
###..#
6 8
..#....#
.####.#.
###.#..#
.##.#.##
.#.##.##
#..##.#.
|
1
6
9
11
15
30
|