A6278. 最大连通块
编程题
普及+/提高
知识点
题目描述
Welcome24ever 有一个由 $n$ 行 $m$ 列组成的网格，每个格子要么是
我们把一些
- 对于集合中的任意两个格子，
可以只在集合内部移动，每一步从当前格子走到一个**与它共享一条边**的格子，
最终从一个格子到达另一个格子。
一个连通块的大小，指的是其中包含的格子数。
在**一次操作**中，Welcome24ever 可以：
- 任意选择一行 $r$（$1 \le r \le n$），或者
- 任意选择一列 $c$（$1 \le c \le m$），
然后将这一整行或这一整列中**所有格子**都改成
请你帮忙计算：在**最多进行一次操作**之后，网格中
.，要么是 #。我们把一些
# 格子组成的集合称为一个 **连通块**，当且仅当：- 对于集合中的任意两个格子，
可以只在集合内部移动，每一步从当前格子走到一个**与它共享一条边**的格子，
最终从一个格子到达另一个格子。
一个连通块的大小，指的是其中包含的格子数。
在**一次操作**中，Welcome24ever 可以：
- 任意选择一行 $r$（$1 \le r \le n$），或者
- 任意选择一列 $c$（$1 \le c \le m$），
然后将这一整行或这一整列中**所有格子**都改成
#。请你帮忙计算：在**最多进行一次操作**之后，网格中
# 连通块的**最大可能大小**是多少。输入格式
输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
接下来依次给出 $t$ 组测试数据，每组数据格式如下：
- 第一行包含两个整数 $n, m$（$1 \le n \cdot m \le 10^6$），表示网格的行数和列数；
- 接下来有 $n$ 行，每行是一个长度为 $m$ 的字符串，只包含字符
保证所有测试用例中 $n \cdot m$ 的**总和**不超过 $10^6$。
接下来依次给出 $t$ 组测试数据，每组数据格式如下：
- 第一行包含两个整数 $n, m$（$1 \le n \cdot m \le 10^6$），表示网格的行数和列数；
- 接下来有 $n$ 行，每行是一个长度为 $m$ 的字符串，只包含字符
. 和 #，表示这一行上每个格子的状态。保证所有测试用例中 $n \cdot m$ 的**总和**不超过 $10^6$。
输出格式
对于每个测试用例，输出一行一个整数，表示 Welcome24ever 在最多进行一次操作后，网格中
# 连通块的**最大可能大小**。输入输出样例
输入 #1
6 1 1 . 4 2 .. #. #. .# 3 5 .#.#. ..#.. .#.#. 5 5 #...# ....# #...# ..... ...## 6 6 .#..#. #..#.. .#...# #.#.#. .#.##. ###..# 6 8 ..#....# .####.#. ###.#..# .##.#.## .#.##.## #..##.#.
输出 #1
1 6 9 11 15 30
说明/提示
## 说明/提示
在第二个测试用例中，Welcome24ever 最优的做法是将第 $2$ 列的所有格子都设置为 '\#'。这样，最大的 '\#' 连通块大小为 $6$。
在第三个测试用例中，Welcome24ever 最优的做法是将第 $2$ 行的所有格子都设置为 '\#'。这样，最大的 '\#' 连通块大小为 $9$。
在第四个测试用例中，Welcome24ever 最优的做法是将第 $4$ 行的所有格子都设置为 '\#'。这样，最大的 '\#' 连通块大小为 $11$。
在第二个测试用例中，Welcome24ever 最优的做法是将第 $2$ 列的所有格子都设置为 '\#'。这样，最大的 '\#' 连通块大小为 $6$。
在第三个测试用例中，Welcome24ever 最优的做法是将第 $2$ 行的所有格子都设置为 '\#'。这样，最大的 '\#' 连通块大小为 $9$。
在第四个测试用例中，Welcome24ever 最优的做法是将第 $4$ 行的所有格子都设置为 '\#'。这样，最大的 '\#' 连通块大小为 $11$。