分数: 425 点
问题陈述
有一个网格 H 行和 W 列。一些单元格(可能为零)包含磁铁。
网格状态表示为 H 字符串 S_1, S_2, \ldots, S_H 长度 W。如果 j- 第一个字符 S_i is #,表明单元格内有一块磁铁 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).
实际上,无法到达其他单元格,因此自由度为 (2,3) is 9.
这是所有没有磁铁的单元格中最大的自由度,所以打印 9.
示例输入 2
3 3 ..# #.. ..#
示例输出 2
1
对于任何没有磁体的单元格,至少一个相邻单元格中存在磁体。
因此,他无法从这些单元中的任何一个移动,因此它们的自由度是 1.
因此,打印 1.