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