8898: 迷宫 (maze)

最近，小Y在玩一款迷宫游戏，游戏是在一个n∗ m的网格上进行的，每个格子可能是空地或者障碍物。游戏一开始，玩家控制的角色位于图中的某块空地上。在游戏过程中，玩家可以用上下左右键控制角色向相邻且没有障碍物的格子移动（当然，角色不能移动到地图之外，也不能对角线移动）。游戏的目标是收集地图上出现的星星（每个星星只能收集一次），收集的数量越多分数越高。小Y刚开了一局游戏，假设游戏时间没有限制，他想知道自己最多能收集到多少个星星。

第一行包含两个正整数n和m，表示游戏的地图包含n行m列。
接下来给出一个n×m的字符矩阵，每个字符可能为以下几种：
● #：表示该位置有障碍物
● . (英文句号)：表示该位置是空地
● *：表示该位置是空地，且生成了一颗星星
● S ：表示该位置是空地，且玩家初始时位于该位置，保证图中有且只有一个S

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

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

2

【数据范围】
对于50%的数据，n，m≤40；
对于100%的数据，1≤n，m≤200。