{"trustable":true,"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":"\n\u003cdiv class\u003d\"panel_content\"\u003e\n 公主被恶魔feng5166绑架了,我们的英雄Ignatius必须拯救我们漂亮的公主。现在他进入了feng5166的城堡。这座城堡是一个巨大的迷宫。为了简化问题,我们假设迷宫是一个N*M的二维数组,左上角是(0,0),右下角是(N-1,M-1)。Ignatius从(0,0)进入,通往feng5166房间的门在(N-1,M-1),也就是我们的目标。城堡里有一些怪物,如果Ignatius遇到它们,他必须杀死它们。以下是一些规则:\n \u003cbr\u003e\n \u003cbr\u003e\n 1.Ignatius只能朝四个方向移动(上、下、左、右),每秒移动一步。一步定义如下:如果当前位置是(x,y),经过一步后,Ignatius只能站在(x-1,y)、(x+1,y)、(x,y-1)或(x,y+1)。\n \u003cbr\u003e\n 2.数组中标记了一些字符和数字。我们将它们定义如下:\n \u003cbr\u003e\n . :Ignatius可以走的地方。\n \u003cbr\u003e\n X :这个地方是一个陷阱,Ignatius不应该走在上面。\n \u003cbr\u003e\n n :这里有一个血量为n的怪物(1\u003c\u003dn\u003c\u003d9),如果Ignatius走在上面,他需要n秒来杀死怪物。\n \u003cbr\u003e\n \u003cbr\u003e\n 你的任务是找出Ignatius到达目标位置所需的最少秒数的路径。你可以假设起始位置和目标位置永远不会是陷阱,并且起始位置不会有怪物。\n \u003cbr\u003e\n\u003c/div\u003e\n"}},{"title":"输入","value":{"format":"HTML","content":"输入包含多个测试用例。每个测试用例以一行包含两个数字N和M(2\u003c\u003dN\u003c\u003d100,2\u003c\u003dM\u003c\u003d100)开头,表示迷宫的大小。然后是一个N*M的二维数组,描述整个迷宫。输入以文件结尾。更多细节请参见样例输入。\n\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,如果Ignatius无法到达目标位置,应输出\"上帝请帮助我们可怜的英雄。\",否则应输出\"到达目标位置需要n秒钟,让我给你指路。\"(n是最少的秒数),并告诉我们的英雄整个路径。每个测试用例后输出一行包含\"FINISH\"。如果有多条路径,本题中任意一条都可以。更多细节请参见样例输出。\n\u003cbr\u003e"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003e输入\u003c/th\u003e\n \u003cth\u003e输出\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 6\r\n.XX.1.\r\n..X.2.\r\n2...X.\r\n...XX.\r\nXXXXX.\r\n5 6\r\n.XX.1.\r\n..X.2.\r\n2...X.\r\n...XX.\r\nXXXXX1\r\n5 6\r\n.XX...\r\n..XX1.\r\n2...X.\r\n...XX.\r\nXXXXX.\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eIt takes 13 seconds to reach the target position, let me show you the way.\r\n1s:(0,0)-\u0026gt;(1,0)\r\n2s:(1,0)-\u0026gt;(1,1)\r\n3s:(1,1)-\u0026gt;(2,1)\r\n4s:(2,1)-\u0026gt;(2,2)\r\n5s:(2,2)-\u0026gt;(2,3)\r\n6s:(2,3)-\u0026gt;(1,3)\r\n7s:(1,3)-\u0026gt;(1,4)\r\n8s:FIGHT AT (1,4)\r\n9s:FIGHT AT (1,4)\r\n10s:(1,4)-\u0026gt;(1,5)\r\n11s:(1,5)-\u0026gt;(2,5)\r\n12s:(2,5)-\u0026gt;(3,5)\r\n13s:(3,5)-\u0026gt;(4,5)\r\nFINISH\r\nIt takes 14 seconds to reach the target position, let me show you the way.\r\n1s:(0,0)-\u0026gt;(1,0)\r\n2s:(1,0)-\u0026gt;(1,1)\r\n3s:(1,1)-\u0026gt;(2,1)\r\n4s:(2,1)-\u0026gt;(2,2)\r\n5s:(2,2)-\u0026gt;(2,3)\r\n6s:(2,3)-\u0026gt;(1,3)\r\n7s:(1,3)-\u0026gt;(1,4)\r\n8s:FIGHT AT (1,4)\r\n9s:FIGHT AT (1,4)\r\n10s:(1,4)-\u0026gt;(1,5)\r\n11s:(1,5)-\u0026gt;(2,5)\r\n12s:(2,5)-\u0026gt;(3,5)\r\n13s:(3,5)-\u0026gt;(4,5)\r\n14s:FIGHT AT (4,5)\r\nFINISH\r\nGod please help our poor hero.\r\nFINISH\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}