Grid and Magnet

题目描述

有一个 $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

3 3
..#
#..
..#

1

提示

$1 \leq H, W \leq 1000$ $H$ 和 $W$ 是整数。 $S_i$ 是由 $.$ 和 # 组成的长度为 $W$ 的字符串。 至少存在一个不含磁铁的格子。记 $(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)$ 的自由度为 $9$。 这是所有不含磁铁的格子中最大的自由度，所以输出 $9$.
对于任意不含磁铁的格子，至少有一个相邻格子含有磁铁。
因此，他不能从这些格子移动，它们的自由度都是 $1$.
因此，输出 $1$.

标签: AtCoder|abc351D

来源

AtCoder|abc351D