← 返回题目列表

Codeforces · 1985/H2

H2. 最大化最大组件(硬版本)

中文机器翻译题面 查看原题

简单版和困难版实际上是不同的问题,因此请完整且仔细地阅读两个问题的陈述。两个版本之间的唯一区别是操作。

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 可以实现的“#”单元格的连接组件的最大可能大小。

示例

输入 #1

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

输出 #1

1
7
11
16
22
36

注意

在第四个测试用例中,Alex 最好将 $$$4$$$ 行和 $$$2$$$ 列中的所有单元格设置为“#”。这样做将导致“#”的最大连通分量的大小为$$$16$$$。

在第五个测试用例中,Alex 最好将 $$$2$$$ 行和 $$$4$$$ 列中的所有单元格设置为“#”。这样做将导致“#”的最大连通分量的大小为$$$22$$$。