A91480.最大连通块

普及+/提高

官方

通过率：0%

时间限制：1.00s

内存限制：128MB

题目描述

Welcome24ever 有一个由 $n$ 行 $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$ 。

输出格式

对于每个测试用例，输出一行一个整数，表示 Welcome24ever 在最多进行一次操作后，网格中 # 连通块的最大可能大小。

输入输出样例

输入#1

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

输出#1

说明/提示

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

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

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

首页