← 返回题单
题单练习 深度优先搜索
← 上一题 下一题 →

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
1
6
9
11
15
30
C++ 编辑器
输入
输出