[ABC351] D - Grid and Magnet

D - Grid and Magnet

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 425 分

题面

有一个 行 列的网格。一些单元格（可能为零）包含磁铁。
网格的状态由 个长度为 的字符串 表示。如果 的第 个字符是 #，则表示位于从上往下数第 行、从左往右数第 列的单元格中有磁铁；如果是 .，则表示该单元格为空。

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

• 如果当前单元格的上下左右相邻的任何一个单元格中含有磁铁，则他无法移动。
• 否则，他可以移动到任何一个上下左右相邻的单元格。
  但他不能离开网格。

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

这里，自由度的定义中，“通过重复移动可以到达的单元格”指的是可以通过一系列移动（可能为零次移动）从初始单元格到达的单元格。不必从初始单元格开始访问所有这样可到达的单元格的移动序列。特别地，每个单元格本身（没有磁铁）总是包括在从该单元格可到达的单元格中。

限制条件

• 和 是整数。
• 是一个由 . 和 # 组成、长度为 的字符串。
• 至少有一个没有磁铁的单元格。

---

输入

输入从标准输入给出，格式如下：

输出

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

---

输入样例 1

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

输出样例 1

9

记 表示位于从上往下数第 行、从左往右数第 列的单元格。如果高桥从 开始，可行的移动包括：

因此，包括他经过的单元格，从 可以到达至少九个单元格。
实际上，没有其他可以到达的单元格，因此 的自由度为 。

这是所有没有磁铁的单元格中的最大自由度，所以输出 。

---

输入样例 2

3 3
..#
#..
..#

输出样例 2

1

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