时间限制: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偷多少个西瓜。
输入描述:
第一行给出两个正整数
)
,其中

是地图的行数,

是地图的列数。
接下来

行长度为

的字符串,表示由‘#’、‘*’和‘.’组成的地图。
输出描述:
输出一个整数,表示恶人zzh能偷到的西瓜的最大数量。
示例2
输入
复制
4 5
#*.*#
**.#*
#*.#*
*.#*#