You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

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

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

输入格式

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

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

• #：表示该位置有障碍物。
• . （英文句号）：表示该位置是空地。
• *：表示该位置是空地，且生成了一颗星星。
• S：表示该位置是空地，且玩家初始时位于该位置，保证图中有且只有一个 S 。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

2

提示

• 对于 50% 的数据：$1 \le N,M \le 40$；
• 对于 100% 的数据：$1 \le N,M \le 200$， 。