{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M \u0026lt;\u003d 200) matrix. There are WALLs, ROADs, and GUARDs in the prison. \n \u003cbr\u003e \n \u003cbr\u003eAngel\u0027s friends want to save Angel. Their task is: approach Angel. We assume that \"approach Angel\" is to get to the position where Angel stays. When there\u0027s a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards. \n \u003cbr\u003e \n \u003cbr\u003eYou have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.) \n \u003cbr\u003e \n\u003c/div\u003e一个N * M (N, M \u003c\u003d 200)的监狱,在监狱中有墙、路和警卫。\u003c/p\u003e\n现在Angel被困在了监狱中,你需要去拯救她。如果你走到了有警卫的点,那么必须杀掉该点的警卫才能顺利通过该点。我们假设你可以移动到上、下、左、右相邻点且所需的时间为1秒,杀掉警卫的时间也为1秒,而且你的能力足够去杀掉监狱中的所有警卫。\u003c/p\u003e\n你很想快点救出Angel,所以请计算出你救出她所需要的最少时间是多少。\n"}},{"title":"Input","value":{"format":"HTML","content":"First line contains two integers stand for N and M. \n\u003cbr\u003e \n\u003cbr\u003eThen N lines follows, every line has M characters. \".\" stands for road, \"a\" stands for Angel, and \"r\" stands for each of Angel\u0027s friend. \n\u003cbr\u003e \n\u003cbr\u003eProcess to the end of the file. \n\u003cbr\u003e第一行有两个整数N和M。\u003c/p\u003e\n接下来N行,每一行M个字符,”.”表示通路,”a”表示Angel所在的位置,并且”r”代表你所在的位置,”x”表示警卫所在的位置\n"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing \"Poor ANGEL has to stay in the prison all his life.\" \n\u003cbr\u003e对于每组样例,输出一个整数,表示你能救出Angel所需的最少时间。如果没有这样的整数可以求出,你要输出\"Poor ANGEL has to stay in the prison all his life.\" "}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e7 8\n#.#####.\n#.a#..r.\n#..#x...\n..#..#.#\n#...##..\n.#......\n........\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e13\u003c/pre\u003e"}}]}