寻宝活动

题目描述

育华学校举办了一场校园寻宝活动，校园可以看作是一个 $n\times m$ 的网格地图，每个格子有不同的状态。其中，有些格子是通路（用 . 表示），有些格子是障碍物（用 # 表示），还有一些格子藏有宝藏（用 * 表示）。活动规则规定，参与者需要从起点（用 S 表示）出发，在不穿过障碍物的前提下，尽可能多地收集宝藏，最后到达终点（用 E 表示）。参与者每一步只能向上下左右四个相邻的格子移动。

现在给定校园地图，要求你计算出参与者最多能收集到的宝藏数量。

输入格式

第一行包含两个正整数 $n$ 和 $m$（$1\leq n\leq 10$，$1\leq m\leq 10$），分别表示地图的行数和列数。 接下来 $n$ 行，每行包含 $m$ 个字符，字符只能是 .、#、*、S 或 E，表示校园地图的布局。

输出格式

输出一个整数，表示参与者最多能收集到的宝藏数量。如果无法从起点到达终点，则输出 -1。

样例

输入样例

4 5
S....
.*.#.
..*..
...E*

输出样例

3

解释

从起点 S 出发，按照合适的路径可以收集到 3 个宝藏并到达终点 E。

数据范围

• 对于 100% 的数据，$1\leq n\leq 10$，$1\leq m\leq 10$。

提示：同一个格子只能经过一次