⼩杨有一⼤⽚荒地 ,可以表⽰为一个 n ⾏ m 列的⽹格图。 ⼩杨想要开垦这块荒地 ,但荒地中一些位置存在杂物 ,对于一块不存在杂物的荒地 ,该荒地可以开垦当且仅当其上 下左右四个⽅向相邻的格⼦均不存在杂物。 ⼩杨可以选择⾄多⼀个位置 ,清除该位置的杂物 ,移除杂物后该位置变为荒地 。⼩杨想知道在清除⾄多⼀个位置的 杂物的情况下 ,最多能够开垦多少块荒地。
第一⾏包含两个正整数 n, m ,含义如题⾯所⽰ 。 之后n⾏ ,每⾏包含一个长度为m且仅包含字符 . 和 # 的字符串 。如果为 . ,代表该位置为荒地 ,如果为 # , 代表该位置为杂物。
输出一个整数 ,代表在清除⾄多一个位置的杂物的情况下 ,最多能够开垦的荒地块数
3 5 ..... .#..# .....
11
样例解释 移除第⼆⾏从左数第⼆块空地的杂物后: ..... ....# .....
第一⾏从左数前 4 块荒地 ,第⼆⾏从左数前 3 块荒地 ,第三⾏从左数前 4 块荒地 ,均可开垦 ,4 + 3 + 4 = 11 。
数据范围 对于全部数据 ,保证有 1 ≤ n, m ≤ 1000。