#3045. 小俞同学的危机

小俞同学的危机

说明

最近小俞同学学习真是太累了,不知不觉就趴在桌子上睡着了。她进入了一个奇怪的梦境,梦到进入了一个迷宫里,这下可愁坏了小俞,最近没吃饱,走也走不动了,只能困在迷宫里面动不了。幸运的是她在梦里梦见了你也在迷宫里,你手里还有一些好吃的,把这些好吃的给她,她就能和你一起跑出去啦。不过迷宫里面有一些大恶魔在,还好你有足够的力量消灭它,但是消灭它也需要一些时间的。好吧,地图给你了,现在快去营救机房女神吧!!

地图是一个四方的地图,你只能从一个格子从上、下、左、右、四个方向走到另一个临近的格子里面,并且花费1个时间单位,消灭恶魔也需要一个单位,有恶魔在的格子,只有消灭了恶魔,才能通行。

输入格式

第一行N和M代表N行M列(1<=N<=200, 1<=M<=200)

接下来N行,没行M个字符,每个字符之间没有空格,整个输入保证没有多余不可见字符。

‘a’代表小俞同学的所在地,‘r'代表你的起始位置,’x'代表恶魔,’#'是墙,'.'代表道路。


输出格式

每组测试样例,输出一个整数,表示从出发到接到小俞同学的步数。由于小俞同学非常的害怕和饿(主要是饿),你要不是用最少的步数到达她身边的话,她就会不高兴,而且最重要的是她不跟你走!!!这样她就永远的困在梦境里面了。。。。。(你的任务也失败了)好惨

不过如果你根本到达不了她身边的话,就输出“I'm so sorry, but I can fly! bye~”(输出不带引号)。

7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........
13

来源

教学题