有一个 H 行 W 列的方格网,部分格子上放着磁石。网格状态由 H 个长度为 W 的字符串 S_1,\dots,S_H 给出:
S_i 的第 j 个字符为 `#` 表示第 i 行第 j 列的格子放了磁石,为 `.` 表示该格为空。
小Z穿着一身**铁甲**,站在某个格子上时,他可以按如下规则移动:
- 若当前格子的**上下左右四个相邻格子中存在磁石**,则他**哪里也去不了**(被磁石吸住,一动都不能动);
- 否则,他可以移动到上下左右相邻的某一个格子(但不能移出网格,也不能走到放有磁石的格子上)。
对每个**没有放磁石**的格子,定义它的**自由度**为:若小Z一开始站在这个格子上,通过反复移动**能够到达的格子个数**(包含起点自己)。
求所有没有放磁石的格子中,自由度的最大值。
> **务必读懂**:「能够到达的格子」指的是**存在某一条移动路线**能到达它,
> **并不要求存在一条路线能一次性把所有这些格子都走遍**。
> 另外,每个空格子自身总是算作「能到达」。
第一行两个整数 H,W(1 \leq H,W \leq 1000),表示网格的行数与列数。
接下来 H 行,第 i 行是一个长度为 W 的、仅由 `.` 与 `#` 组成的字符串 S_i。
输出所有没有放磁石的格子中,自由度的最大值。
3 5 .#... ..... .#..#
9
3 3 ..# #.. ..#
1
**样例1说明**:把行从上到下、列从左到右编号。站在 (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)。
数据范围:
- 1\le H,W\le 1000;
- H,W 为整数;
- S_i 是仅由 `.` 与 `#` 组成的长度 W 的字符串;
- **至少存在一个**没有放磁石的格子。
| 时间限制 | 1 秒 |
| 内存限制 | 128 MB |