J8 习题-5 拯救小王子

题目描述

一个 $N$ 行 $M$ 列的矩阵，其中 .代表路，#代表墙，a代表小王子，r代表龙骑士，x 代表守卫。 龙骑士可以上下左右的走动，每次移动需要花费一个单位时间，如果遇到守卫就要击倒他，每次击倒守卫，需要另外花费一个单位时间（龙骑士的体力无限，可以击倒全部守卫）。

请问，龙骑士最少要花多少个时间，才能救出小王子。

如果不能，则输出 Poor ANGEL has to stay in the prison all his life.

输入格式

多组数据， 每组数据第一行给出 $N$ 和 $M$ ，表示 $N*M$ 的矩阵；接下来一个字符矩阵，如题意描述。

输出格式

如果能救出小王子，输入最小的时间代价，如不能，输出 Poor ANGEL has to stay in the prison all his life. 。

样例输入

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

样例输出

13

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据有： $1 \leq N,M \leq 200$ 。