Codeforces Round 952 (Div. 4) |
---|
Закончено |
Простая и сложная версии фактически представляют собой разные задачи, поэтому внимательно прочитайте условия обеих задач. Единственное различие между двумя версиями — это применяемая операция.
У Алекса есть матрица из $$$n$$$ строк и $$$m$$$ столбцов, состоящая из символов '.' и '#'. Набор '#' ячеек формирует компоненту связности, если из любой ячейки в этом наборе можно достичь любую другую ячейку в этом наборе, перемещаясь только в другую ячейку набора, которая имеет общую сторону. Размер компоненты связности — это количество ячеек в наборе.
За одну операцию Алекс выбирает любую строку $$$r$$$ ($$$1 \le r \le n$$$) или любой столбец $$$c$$$ ($$$1 \le c \le m$$$), затем устанавливает каждую ячейку в строке $$$r$$$ или столбце $$$c$$$ равной '#'. Помогите Алексу найти максимально возможный размер наибольшей компоненты связности из ячеек '#', который он может достичь после выполнения операции не более одного раза.
Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \cdot m \le 10^6$$$) — количество строк и столбцов матрицы.
Следующие $$$n$$$ строк содержат по $$$m$$$ символов. Каждый символ может быть '.' или '#'.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам не превышает $$$10^6$$$.
Для каждого теста выведите одно целое число — максимально возможный размер компоненты связности из ячеек '#', который может достичь Алекс.
61 1.4 2..#.#..#3 5.#.#...#...#.#.5 5#...#....##...#........##6 6.#..#.#..#...#...##.#.#..#.##.###..#6 8..#....#.####.#.###.#..#.##.#.##.#.##.###..##.#.
1 6 9 11 15 30
Во втором примере для Алекса оптимально установить все ячейки в столбце $$$2$$$ равными '#'. Это приведет к тому, что наибольшая компонента связности из '#' будет иметь размер $$$6$$$.
В третьем примере для Алекса оптимально установить все ячейки в строке $$$2$$$ равными '#'. Это приведет к тому, что наибольшая компонента связности из '#' будет иметь размер $$$9$$$.
В четвертом примере для Алекса оптимально установить все ячейки в строке $$$4$$$ равными '#'. Это приведет к тому, что наибольшая компонента связности из '#' будет иметь размер $$$11$$$.
Название |
---|