2317 - 地图探索
描述

有一个用字符类型表示的 HW 列的地图 S如果 S_{i,j} 是字符 `.` 则代表这一格是空地,如果是 `#` 则代表这一格上有一个磁铁。

现有一个小人从一个格子上出发,每次可以到达与之相邻(上、下、左、右)的四个格子,但如果有一个磁铁与之相邻(上下左右的四个格子中至少有一个磁铁)他就不能动了。

求小人从某一格出发,经过任意多次运动,可以到达的格子的最大数量。

输入

第一行两个数字, HW

接下来一个 HW 列的字符矩阵

输出

能走过去的最大数量

样例

输入

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

输出

9

输入

3 3
..#
#..
..#

输出

1
提示

- 1\leq\ H,W\leq\ 1000

样例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


题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 107
通过次数 12