有一个用字符类型表示的 H 行 W 列的地图 S,如果 S_{i,j} 是字符 `.` 则代表这一格是空地,如果是 `#` 则代表这一格上有一个磁铁。
现有一个小人从一个格子上出发,每次可以到达与之相邻(上、下、左、右)的四个格子,但如果有一个磁铁与之相邻(上下左右的四个格子中至少有一个磁铁)他就不能动了。
求小人从某一格出发,经过任意多次运动,可以到达的格子的最大数量。
第一行两个数字, H 行 W 列
接下来一个 H 行 W 列的字符矩阵
能走过去的最大数量
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 。