问题 22847. -- 掉线城与虚弱勇士

22847: 掉线城与虚弱勇士

时间限制: 5 Sec  内存限制: 128 MB
献花: 3  解决: 2
[献花][花圈]

题目描述

去年的121日的ACM校赛后,小明玩的《轩辕剑天之痕》已经被他通关了。他顺便也学习了游戏编程中很重要的搜索算法,毕竟很多公司笔试和面试都会考察。

现在大二的小明很喜欢玩一种网络游戏——《掉线城与虚弱勇士》

在这个游戏的迷宫中,你必须争分夺秒的从迷宫的入口走到出口,否则就会遇到掉线这种超级大BOSS把你一刀秒杀。在这种掉线的环境中,每走一步路需要花费一分钟的时间。

需要注意的是,迷宫中会有一些守卫,这些守卫很弱小,但是他们会拖延你一分钟的时间,使你更加接近掉线。

你要做的是在最短的时间中冲出这个迷宫,计算出这个最短的时间。

PS:守卫不一定要打,想办法在最短时间内冲出迷宫才是第一任务。

 

输入

第一行是一个整数T,表示测试数据的组数(1<T<5)

对每一组测试样例,第一行为NM,表示一个N*M的矩阵,即迷宫本身。(N,M<=100)

对迷宫来说,字符"." 代表路, "a" 小明的角色起始的位置,  "r" 代表出口的位置, "x"代表守卫的位置。

输出

对每组测试数据,输出一行数据,表示最短花费的时间。

如果小明根本走不出去迷宫,请输出“Poor XIAOMING has to stay in the prison all his life.

样例输入

1
7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........

样例输出

13

提示

来源

[献花][花圈]