103513: [Atcoder]ABC351 D - Grid and Magnet

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$.

问题描述

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

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

• 如果当前单元格的垂直或水平相邻单元格中有磁铁，他无法移动。
• 否则，他可以移动到任意一个垂直或水平相邻的单元格。
  但是，他不能离开网格。

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

在自由度的定义中，“通过反复移动可以到达的单元格”是指可以通过从初始单元格出发的一系列移动（可能不进行移动）到达的单元格。不需要从初始单元格开始存在一条移动序列可以访问所有这样的可到达单元格。具体来说，每个单元格本身（没有磁铁）始终包含在可以从该单元格到达的单元格中。

约束

• $1 \leq H, W \leq 1000$
• $H$和$W$是整数。
• $S_i$是由.和#组成的长度为$W$的字符串。
• 至少有一个单元格没有磁铁。

输入

输入从标准输入以以下格式给出：

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$

输出

打印所有没有磁铁的单元格中的最大自由度。

样例输入1

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

样例输出1

9

令$(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

3 3
..#
#..
..#

样例输出2

1

对于任何没有磁铁的单元格，其相邻的单元格中至少有一个有磁铁。
因此，他无法从这些单元格中移动，所以它们的自由度为$1$。
因此，打印$1$。