4227: Grid and Magnet

# Grid and Magnet ### 内存 1024MB ### 时间 2S ## 题目描述 有一个 $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$ ## 输出格式 输出所有没有磁铁的单元格中最大的自由度。 ## 输入输出样例 ### 输入样例1 ``` 3 5 .#... ..... .#..# ``` ### 输出样例1 ``` 9 ``` ### 输入样例2 ``` 3 3 ..# #.. ..# ``` ### 输出样例2 ``` 1 ``` ## 数据范围与提示 【样例1说明】 让 $(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$。 【样例2说明】 对于任何没有磁铁的单元格，其相邻单元格中至少有一个包含磁铁。 因此，他无法从这些单元格中的任何一个移动，所以它们的自由度都是 $1$。 所以输出 $1$。 【数据范围】 $1 \leq H, W \leq 1000$ $H$ 和 $W$ 是整数 $S_i$ 是长度为 $W$ 的由 `.` 和 `#` 组成的字符串 至少有一个单元格没有磁铁 ## 题目来源 ABC351D