2104: 迷宫(maze)

题目描述


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

输入


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

输出


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

样例输入


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

样例输出


2

提示


【数据范围】
对于50%的数据,n,m<=40;
对于100%的数据,1<=m,m<=200

来源/分类


2019年海淀区挑战赛小学组

请先 登录 后评论
  • 0 关注
  • 0 收藏,896 浏览
  • 轩爸 提出于 2019-08-02 22:38