掉线城与虚弱勇士

<p class="p0" style="text-indent:21pt;"> <span style="font-size:10.5pt;font-family:'宋体';">去年的<span>12</span><span>月</span><span>1</span><span>日的</span><span>ACM</span><span>校赛后，小明玩的《轩辕剑天之痕》已经被他通关了。他顺便也学习了游戏编程中很重要的搜索算法，毕竟很多公司笔试和面试都会考察。</span></span><span style="font-size:10.5pt;font-family:'宋体';"></span> </p> <p class="p0"> <span style="font-size:10.5pt;font-family:'宋体';">现在大二的小明很喜欢玩一种网络游戏——《掉线城与虚弱勇士》</span> </p> <p class="p0"> <img alt="" src="http://tk.hustoj.com/attached/image/20140520/20140520132221_54541.jpg" /> </p> <p class="p0" style="text-indent:21pt;"> <span style="font-size:10.5pt;font-family:'宋体';">在这items游戏的迷宫中，你必须争points夺seconds的从迷宫的入口走到出口，否则就会遇到掉线这种超级大<span>BOSS</span><span>把你一刀seconds杀。在这种掉线的环境中，每走一步路需要花费一points钟的时间。</span></span><span style="font-size:10.5pt;font-family:'宋体';"></span> </p> <p class="p0" style="text-indent:21pt;"> <span style="font-size:10.5pt;font-family:'宋体';">需要注意的是，迷宫中会有一些守卫，这些守卫很弱小，但是他们会拖延你一points钟的时间，使你更加接近掉线。</span><span style="font-size:10.5pt;font-family:'宋体';"></span> </p> <p class="p0" style="text-indent:21pt;"> <span style="font-size:10.5pt;font-family:'宋体';">你要做的是在最短的时间中冲出这items迷宫，计算出这items最短的时间。</span><span style="font-size:10.5pt;font-family:'宋体';"></span> </p> <p class="p0" style="text-indent:21pt;"> <span style="font-size:10.5pt;font-family:'宋体';">PS<span>：守卫不一定要打，想办法在最短时间内冲出迷宫才是Page 一任务。</span></span><span style="font-size:10.5pt;font-family:'宋体';"></span> </p> <p class="p0"> &nbsp; </p> <span style="font-size:10.5pt;font-family:'宋体';"></span>

<p class="p0"> <span style="font-size:10.5pt;font-family:'宋体';">Page 一行是一items整数<span>T</span><span>，表示测试数据的组数（</span><span>1&lt;T&lt;5)</span></span><span style="font-size:10.5pt;font-family:'宋体';"></span> </p> <p class="p0"> <span style="font-size:10.5pt;font-family:'宋体';">对每一组测试样例，Page 一行为<span>N</span><span>，</span><span>M</span><span>，表示一items</span><span>N*M</span><span>的矩阵，即迷宫本身。</span><span>(N,M&lt;=100)</span></span><span style="font-size:10.5pt;font-family:'宋体';"></span> </p> <p class="p0"> <span style="font-size:10.5pt;font-family:'宋体';">对迷宫来说，字符<span>"."&nbsp;</span><span>代表路</span><span>,&nbsp;"a"&nbsp;</span><span>小明的角色起始的位置</span><span>,&nbsp;&nbsp;"r"&nbsp;</span><span>代表出口的位置，&nbsp;</span><span>"x"</span><span>代表守卫的位置。</span></span><span style="font-size:10.5pt;font-family:'宋体';"></span> </p>

<p class="p0"> <span style="font-size:10.5pt;font-family:'宋体';">对每组测试数据，输出一行数据，表示最短花费的时间。</span><span style="font-size:10.5pt;font-family:'宋体';"></span> </p> <p class="p0"> <span style="font-size:10.5pt;font-family:'宋体';">如果小明根本走不出去迷宫，请输出“</span><span style="font-size:12pt;font-family:'宋体';">Poor&nbsp;</span><span style="font-size:12pt;font-family:'宋体';">XIAOMING</span><span style="font-size:12pt;font-family:'宋体';">&nbsp;has&nbsp;to&nbsp;stay&nbsp;in&nbsp;the&nbsp;prison&nbsp;all&nbsp;his&nbsp;life.</span><span style="font-size:12pt;font-family:'宋体';">”</span><span style="font-size:10.5pt;font-family:'宋体';"></span> </p>