题目描述

简单版和困难版实际上是不同的问题，请完整且仔细阅读两个版本的题目描述。两者唯一的区别在于操作方式。

Alex 有一个由 $n$ 行 $m$ 列组成的网格，网格中的每个格子要么是 '.'，要么是 '#'。一组 '#' 格子构成一个连通块，如果从该集合中的任意一个格子出发，只通过与集合中其他格子相邻的格子（共享一条边），可以到达集合中的任意其他格子。连通块的大小指的是该集合中格子的数量。

每次操作中，Alex 可以任选一行 $r$（$1 \le r \le n$）或一列 $c$（$1 \le c \le m$），然后将第 $r$ 行或第 $c$ 列的所有格子都设置为 '#'。请你帮助 Alex 求出，在最多进行一次操作后，'#' 连通块的最大可能大小是多少。

输入格式

输入的第一行为一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行为两个整数 $n$ 和 $m$（$1 \le n \cdot m \le 10^6$），分别表示网格的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个字符，每个字符为 '.' 或 '#'。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一个整数，表示 Alex 能够获得的 '#' 连通块的最大可能大小。

样例

6
1 1
.
4 2
..
#.
#.
.#
3 5
.#.#.
..#..
.#.#.
5 5
#...#
....#
#...#
.....
...##
6 6
.#..#.
#..#..
.#...#
#.#.#.
.#.##.
###..#
6 8
..#....#
.####.#.
###.#..#
.##.#.##
.#.##.##
#..##.#.

1
6
9
11
15
30

样例说明

在第二个测试用例中，Alex 最优的做法是将第 $2$ 列的所有格子都设置为 '#'。这样，最大的 '#' 连通块大小为 $6$。

在第三个测试用例中，Alex 最优的做法是将第 $2$ 行的所有格子都设置为 '#'。这样，最大的 '#' 连通块大小为 $9$。

在第四个测试用例中，Alex 最优的做法是将第 $4$ 行的所有格子都设置为 '#'。这样，最大的 '#' 连通块大小为 $11$。

由 ChatGPT 4.1 翻译

来源

Codeforces 1985H1，英文题名 Maximize the Largest Component (Easy Version)。