{"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":"\u003cdiv class\u003d\"panel_content\"\u003e《西游记》(又名《悟空传》)是中国文学四大名著之一,是明朝时期吴承恩所著。小说讲述了孙悟空、猪八戒、沙僧三位弼马温法师前往印度取经的故事。\u003cbr\u003e\u003cbr\u003e在这段旅程中,法师常常被恶魔所抓获。大部分恶魔企图吃掉法师以获得长生不老,但也有一些女妖只是因为法师英俊而想要嫁给他。因此,与恶魔战斗并拯救法师成了孙悟空的主要任务。\u003cbr\u003e\u003cbr\u003e曾经,法师被骷髅精抓获。骷髅精住在一个宫殿里,把法师关在一个房间里。孙悟空设法进入了宫殿。但要解救法师,孙悟空可能需要找到一些钥匙并杀死途中的一些蛇。\u003cbr\u003e\u003cbr\u003e这座宫殿可以被描述为一个字符矩阵。每个字符代表一个房间。在这个矩阵中,\u0027K\u0027代表孙悟空的起始位置,\u0027T\u0027代表法师的位置,\u0027S\u0027代表有蛇的房间。请注意,矩阵中只有一个\u0027K\u0027和一个\u0027T\u0027,最多有五条蛇。此外,\u0027.\u0027代表一个空房间,\u0027#\u0027代表一个无法进入的致命房间。\u003cbr\u003e\u003cbr\u003e可能有不同种类的钥匙散落在房间里,但每个房间最多只有一个钥匙。最多有9种钥匙。有钥匙的房间用数字(从\u00271\u0027到\u00279\u0027)表示。例如,\u00271\u0027代表第一种钥匙的房间,\u00272\u0027代表第二种钥匙的房间,\u00273\u0027代表第三种钥匙的房间......等等。为了解救法师,孙悟空必须获得所有种类的钥匙(换句话说,每种钥匙至少要有一把)。\u003cbr\u003e\u003cbr\u003e每一步,孙悟空可以向四个方向(北、西、南、东)移动到相邻的房间(除了致命的房间),每步走一分钟。如果他进入了一间有蛇的房间,他必须杀死蛇。杀死一条蛇也需要一分钟。如果孙悟空进入了一个有第N种钥匙的房间,只有在他已经获得了第1种、第2种...直到第N-1种钥匙时,他才能获得那把钥匙。换句话说,孙悟空必须先获得第N种钥匙再获得第N+1种钥匙(N≥1)。如果孙悟空得到了他需要的所有钥匙并进入了关押法师的房间,任务就算完成了。如果孙悟空没有获得足够的钥匙,他仍然可以通过法师的房间。由于孙悟空是一个急性子的猴子,他希望尽快解救法师。请计算孙悟空解救法师所需的最短时间。\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"有多个测试用例。\u003cbr\u003e\u003cbr\u003e对于每个用例,第一行包括两个整数N和M(0<N≤100,0≤M≤9),表示宫殿是一个N×N的矩阵,孙悟空需要M种钥匙(第1种、第2种...第M种)。\u003cbr\u003e\u003cbr\u003e然后是N×N矩阵。\u003cbr\u003e\u003cbr\u003e输入以N \u003d 0和M \u003d 0结束。"}},{"title":"Output","value":{"format":"HTML","content":"对于每个测试用例,打印孙悟空解救法师所需的最短时间(以分钟为单位)。如果孙悟空无法完成任务,则打印“impossible”(不带引号)。"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 1\r\nK.S\r\n##1\r\n1#T\r\n3 1\r\nK#T\r\n.S#\r\n1#.\r\n3 2\r\nK#T\r\n.S.\r\n21.\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\nimpossible\r\n8\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}