← 返回题目

题库练习最大连通块

← 上一题下一题 →

A6278 | $最大连通块$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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

C++ 编辑器

输入

输出