题目描述

最近，小 Y 在玩一款迷宫游戏，游戏是在一个 n ∗ m 的网格上进行的，每个格子可能是空地或者障碍物。

游戏一开始，玩家控制的角色位于图中的某块空地上。在游戏过程中，玩家可以用上下左右键控制角色向相邻且没有障碍物的格子移动（当然，角色不能移动到地图之外，也不能对角线移动）。

游戏的目标是收集地图上出现的星星（每个星星只能收集一次），收集的数量越多分数越高。

小 Y 刚开了一局游戏，假设游戏时间没有限制，他想知道自己最多能收集到多少个星星。

输入格式

第一行包含两个正整数 n 和 m ，表示游戏的地图包含 n 行 m 列。

接下来给出一个n×m的字符矩阵，每个字符可能为以下几种：

1. #：表示该位置有障碍物

2. . (英文句号)：表示该位置是空地

3. *：表示该位置是空地，且生成了一颗星星

4. S：表示该位置是空地，且玩家初始时位于该位置，保证图中有且只有一个 S

数据范围

对于 50% 的数据，n，m ≤ 40；

对于 100% 的数据，1≤n，m≤200。

输出格式

一个整数，表示最多能收集到多少颗星星。

样例

4 8
..#...*.
*.#.S#..
######..
.*..#.*.

2