{"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\"\u003eIgnatius has been captured by the demon king again (can\u0027t understand why the demon king likes him so much)......\u003cbr\u003e\u003cbr\u003eThis time, the demon king, having learned from the previous experience, has locked Ignatius in a n*m dungeon and installed locked doors in certain places in the dungeon, with the keys hidden in other places. Initially, Ignatius is trapped at position (sx, sy), and the exit door is located at position (ex, ey). Ignatius can only move from one coordinate to one of its four adjacent coordinates per minute. The demon king inspects the dungeon every t minutes, and if he finds Ignatius not at his original position, he will bring him back. After several attempts, Ignatius has drawn the map of the entire dungeon. Now, he needs your help to calculate if he can successfully escape again. It is considered a successful escape as long as he reaches the exit before the demon king\u0027s next inspection. If the demon king returns and Ignatius has just reached the exit or has not yet reached the exit, it is considered a failed escape.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of each test case contains three integers n, m, and t (2≤n,m≤20, t\u003e0). The next n lines consist of m characters representing the dungeon map, including:\u003cbr\u003e\u003cbr\u003e. representing a path\u003cbr\u003e* representing a wall\u003cbr\u003e@ representing Ignatius\u0027s starting position\u003cbr\u003e^ representing the exit of the dungeon\u003cbr\u003eA-J representing locked doors, with corresponding keys a-j\u003cbr\u003ea-j representing keys, with corresponding doors A-J\u003cbr\u003e\u003cbr\u003eThere is a blank line between each test case.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, if Ignatius can successfully escape, output the number of minutes needed to leave. If not, output -1.\u003cbr\u003e"}},{"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\u003e4 5 17\r\n@A.B.\r\na*.*.\r\n*..*^\r\nc..b*\r\n\r\n4 5 16\r\n@A.B.\r\na*.*.\r\n*..*^\r\nc..b*\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e16\r\n-1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}