AT_abc351_d [ABC351D] Grid and Magnet

有一个 $H$ 行 $W$ 列的格子，其中有若干个（也可能为 $0$ 个）格子上放置了磁铁。 格子的状态由 $H$ 个长度为 $W$ 的字符串 $S_1,S_2,\ldots,S_H$ 表示，$S_i$ 的第 $j$ 个字符为 `#` 时，表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子上放置了磁铁，为 `.` 时表示该格子上没有放置任何东西。 高桥君穿着铁制盔甲，在某个格子时可以按如下方式移动： - 如果当前格子的上下左右相邻的任意一个格子上放置了磁铁，则无法移动到任何地方。 - 否则，可以选择上下左右相邻的任意一个格子并移动到该格子。 但不能移动到格子外面。 对于没有放置磁铁的每个格子，定义该格子的自由度为“最初高桥君在该格子时，从该格子出发通过多次移动能够到达的格子的数量”。 请你求出所有没有放置磁铁的格子中，自由度的最大值。 需要注意的是，在自由度的定义中，“能够通过多次移动到达的格子”指的是，从最初所在的格子出发，通过若干次（也可以为 $0$ 次）移动能够到达的格子，不要求存在一种移动方式能够遍历所有这些格子。特别地，每个没有放置磁铁的格子本身总是包含在“能够到达的格子”之中。

输入按以下格式从标准输入读入。 > $H$ $W$ > $S_1$ > $S_2$ > $\vdots$ > $S_H$

请输出所有没有放置磁铁的格子中，自由度的最大值。

## 限制条件 - $1 \leq H, W \leq 1000$ - $H, W$ 为整数 - $S_i$ 是仅由 `.` 和 `#` 组成的长度为 $W$ 的字符串 - 至少存在一个没有放置磁铁的格子 ## 样例解释 1 用 $(i, j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。 当高桥君最初在 $(2,3)$ 时，移动的例子有如下几种： - $(2,3) \to (2,4) \to (1,4) \to (1,5) \to (2,5)$ - $(2,3) \to (2,4) \to (3,4)$ - $(2,3) \to (2,2)$ - $(2,3) \to (1,3)$ - $(2,3) \to (3,3)$ 因此，包括途中经过的格子在内，高桥君从 $(2,3)$ 至少可以到达 $9$ 个格子。 另一方面，无法到达其他格子，因此 $(2,3)$ 的自由度为 $9$。 这是所有没有放置磁铁的格子中自由度的最大值，因此输出 $9$。 ## 样例解释 2 对于没有放置磁铁的任意格子，其上下左右相邻的格子中至少有一个放置了磁铁。 因此，从没有放置磁铁的任意格子都无法移动，自由度为 $1$。 所以输出 $1$。 由 ChatGPT 4.1 翻译