Problem 3532 --收集圣物

3532: 收集圣物

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $198$ 正确数量 $43$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

在一个策略游戏中,僧侣可以收集圣物,放入修道院中,以生产黄金。因此,圣物对赢得游戏的胜利很重要。

某个僧侣正处于一个长为n宽为m的矩形迷宫中,迷宫的四周都是墙壁,不可移动,迷宫中圣物可能有若干个。为了降低游戏难度,僧侣只需要发现任意一个圣物,就能完成任务

迷宫有若干扇门,同时在迷宫的一些地方会有钥匙每一把钥匙都只能使用一次,每一次可以开一扇门。即:一旦你通过一扇门后,门将自动关闭,如果想要再次打开这扇门,你需要再使用一把钥匙去打开它,通过之后门还将自动关闭。

僧侣移速缓慢,每秒能够向上下左右四个方向各移动一个单位。不过开门以及拾取钥匙不耗费时间。

输入这个迷宫,输出最快多少秒能够发现一个圣物。如果僧侣无法收集任何圣物,输出“Bug Maze!!!”。

第一行两个正整数n,m(n,m<=25)。
接下来n行,每行m个字符,字符含义如下:
‘#’ -- 该位置为墙或者障碍。
‘.’ -- 该位置可以正常行走。
‘K’ -- 该位置有一把钥匙。
‘D’ -- 该位置有一扇门。
‘S’ --起始位置。‘S’仅有一个。
‘E’ – 圣物位置。‘E’可能有多个。
数据保证钥匙的数量<=10。
仅一行,输出离开的最少时间。 如不能离开,输出“Bug Maze!!!”。
5 6
##.S#E
##.###
##.K##
E##D##
##E.##
7

推荐代码 查看3532 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$2 $ms] 2019000000 687996 2020-12-23 15:43:35
内存最少[$2092 $KB] 2019000000 687996 2020-12-23 15:43:35
第一AC yuanbao 629373 2020-10-20 00:38:59
第一挑战 yuanbao 629345 2020-10-20 00:26:56

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛