{"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":"Nina被Monipi抓住了!Monipi把Nina关进了禁闭室。禁闭室被描述为一个N*M(N,M\u003c\u003d200)矩阵。禁闭室里有墙,有路,有警卫。 Nina的朋友们想救Nina。他们的任务是:接近Nina。我们假设“接近Nina”就是到达Nina停留的位置。当有警卫在格子里时,朋友们必须杀了他(或她?)才能进入格子里。我们假设上、下、右、左移动需要1个单位的时间,杀死一个警卫也需要1个单位的时间。我们有足够的力量杀死所有的警卫。 你必须计算接近Nina的最短的时间(当然,我们只能上下左右移动到边界内的相邻网格。)"}},{"title":"Input","value":{"format":"HTML","content":"第一行包含两个整数,分别代表N和m。\n接着是N行,每行有M个字符。“.”代表路,“a”代表Nina,“r”代表Nina的每一个朋友,\"x\"表示警卫.\n处理到文件末尾。"}},{"title":"Output","value":{"format":"HTML","content":"对于每个测试用例,您的程序应该输出一个整数,表示所需的最小时间。如果这样的数字不存在,你应该输出一行\"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"}},{"title":"提示","value":{"format":"HTML","content":"朋友不止一个,可以反过来思考。"}}]}