Score: $425$ points

问题陈述

有一个 $H$ 行 $W$ 列的网格。一些单元格（可能是零个）包含磁铁。 网格的状态由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 表示。如果 $S_i$ 中的第 $j$ 个字符是 #，则表示在从顶部数第 $i$ 行和从左侧数第 $j$ 列的单元格中有一个磁铁；如果是 .，则表示该单元格为空。

穿着铁甲的高桥可以在网格中按照以下方式移动：

• 如果当前单元格的垂直或水平相邻单元格中有任何单元格包含磁铁，他就完全不能移动。
• 否则，他可以移动到任何一个垂直或水平相邻的单元格。 然而，他不能离开网格。

对于没有磁铁的每个单元格，定义其自由度为他可以通过反复从该单元格移动到达的单元格数量。在没有磁铁的所有单元格中找到最大自由度。

在这里，自由度的定义中，“通过反复移动到达的单元格”意味着可以从初始单元格通过一系列移动（可能是零次移动）到达的单元格。没有必要从初始单元格开始就有一系列移动访问所有这些可达单元格。具体来说，每个单元格本身（没有磁铁）总是包含在从该单元格可达的单元格中。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There is a grid of $H$ rows and $W$ columns. Some cells (possibly zero) contain magnets.
The state of the grid is represented by $H$ strings $S_1, S_2, \ldots, S_H$ of length $W$. If the $j$-th character of $S_i$ is #, it indicates that there is a magnet in the cell at the $i$-th row from the top and $j$-th column from the left; if it is ., it indicates that the cell is empty.

Takahashi, wearing an iron armor, can move in the grid as follows:

• If any of the cells vertically or horizontally adjacent to the current cell contains a magnet, he cannot move at all.
• Otherwise, he can move to any one of the vertically or horizontally adjacent cells.
  However, he cannot exit the grid.

For each cell without a magnet, define its degree of freedom as the number of cells he can reach by repeatedly moving from that cell. Find the maximum degree of freedom among all cells without magnets in the grid.

Here, in the definition of degree of freedom, "cells he can reach by repeatedly moving" mean cells that can be reached from the initial cell by some sequence of moves (possibly zero moves). It is not necessary that there is a sequence of moves that visits all such reachable cells starting from the initial cell. Specifically, each cell itself (without a magnet) is always included in the cells reachable from that cell.

Constraints

• $1 \leq H, W \leq 1000$
• $H$ and $W$ are integers.
• $S_i$ is a string of length $W$ consisting of . and #.
• There is at least one cell without a magnet.

Input

The input is given from Standard Input in the following format:

$H$ $W$

$S_1$

$S_2$

$\vdots$

$S_H$

Output

Print the maximum degree of freedom among all cells without magnets.

Sample Input 1

3 5
.#...
.....
.#..#

Sample Output 1

9

Let $(i,j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left. If Takahashi starts at $(2,3)$, possible movements include:

• $(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)$

Thus, including the cells he passes through, he can reach at least nine cells from $(2,3)$.
Actually, no other cells can be reached, so the degree of freedom for $(2,3)$ is $9$.

This is the maximum degree of freedom among all cells without magnets, so print $9$.

Sample Input 2

3 3
..#
#..
..#

Sample Output 2

1

For any cell without a magnet, there is a magnet in at least one of the adjacent cells.
Thus, he cannot move from any of these cells, so their degrees of freedom are $1$.
Therefore, print $1$.