P13599 [NWRRC 2022] Bricks in the Wall

Bob 正在用砖块装饰一个工业风格的矩形墙面。该墙面由 $n \times m$ 个单元格组成。有些单元格已经被砖块占据，其余单元格为空。 Bob 想在这面墙上再添加至多两块砖。新砖的宽度必须为 $1$ 单位，长度可以是任意正整数。每块砖只能水平或垂直放置，因此每块新砖会占据同一行或同一列中若干连续的空单元格。此外，这两块砖不能相交，即不能占据同一个单元格。 Bob 最多能在这面墙上添加的两块新砖的长度之和是多少？

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示墙的高度和宽度（$1 \le n, m$；$n \cdot m \le 10^6$）。 接下来的 $n$ 行，每行包含 $m$ 个字符，描述墙的状态。被砖块占据的单元格用 $\tt{\#}$ 表示，空单元格用 $\tt{.}$ 表示。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。

对于每个测试用例，输出一个整数，表示最多能添加的两块新砖的长度之和。

由 ChatGPT 4.1 翻译