CF1985H1.Maximize the Largest Component (Easy Version)

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

简单版和困难版实际上是不同的问题，请完整且仔细阅读两个版本的题目描述。两者唯一的区别在于操作方式。

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

说明/提示

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

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

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

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页