网格与磁铁

题目描述

有一个 $H$ 行 $W$ 列的网格。有些格子(可能没有)放有磁铁。

网格的状态由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 表示。如果 $S_i$ 的第 $j$ 个字符是 #,表示从上方数第 $i$ 行、从左数第 $j$ 列的格子放有磁铁;如果是 .,表示该格子为空。

身穿铁甲的高桥君可以按以下规则在网格中移动:

• 如果当前格子上下左右任意一个相邻格子中有磁铁,则他完全无法移动。
• 否则,他可以移动到上下左右任意一个相邻格子。

但是,他不能走出网格。

对于每个没有磁铁的格子,定义其「自由度」为从该格子出发反复移动所能到达的格子数。求网格中所有没有磁铁的格子自由度的最大值。

这里,在自由度的定义中,「反复移动所能到达的格子」指的是从初始格子出发,通过某个移动序列(可以是零次移动)能够到达的格子。并不要求存在一个从初始格子出发能遍历所有这些可达格子的移动序列。具体地,每个没有磁铁的格子自身总是包含在从该格子出发可达的格子中。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

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

样例

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

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。

3 3
..#
#..
..#

1

对于任意没有磁铁的格子,其上下左右至少有一个相邻格子中有磁铁。

因此,他无法从任何这样的格子移动,这些格子的自由度都是 $1$。

所以输出 1。

数据范围

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