南湖的瓜
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

某次偶然的机会,小c在南湖边发现了一块宝地,想实现西瓜自由的小c决定在这里种一片西瓜。西瓜长势喜人,瓜地一片丰收,但是好景不长,恶人zzh不知道从哪得到了这个消息,并决定找个夜黑风高的夜晚去偷小c的瓜,但是瓜不是这么好偷的,聪明的小c在瓜地埋了很多地雷。恶人zzh也很狡猾,他贿赂小c的友人小罗,得到了小c瓜地的地图,并且苦练了一项技能,能从某个位置直接跳到另一个位置。但是由于zzh是懒狗,所以他的技能只能使用一次。

现给出一个的地图,代表小c的瓜地,‘#代表地雷,‘*’代表西瓜,‘.’代表空地,恶人zzh不能踩到地雷,不然他就被炸死了,恶人zzh能从任意位置开始偷瓜,他也能从任意位置选择离开,但是除了使用技能的时候,他只能上下左右走动。请聪明的你算一算小c最多能被恶人zzh偷多少个西瓜。

输入描述:

第一行给出两个正整数,其中n是地图的行数,m是地图的列数。

接下来n行长度为m的字符串,表示由‘#’、‘*’和‘.’组成的地图。

输出描述:

输出一个整数,表示恶人zzh能偷到的西瓜的最大数量。
示例1

输入

复制
3 4
*#*.
.*#.
##**

输出

复制
5
示例2

输入

复制
4 5
#*.*#
**.#*
#*.#*
*.#*#

输出

复制
8