{"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":"PLAIN","content":" Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)…… 这次魔王汲取了上次的教训,把Ignatius关在一个n*m的地牢里,并在地牢的某些地方安装了带锁的门,钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置,离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次,若发现Ignatius不在原位置便会杀死他,但魔王为他准备了一个复活点(因为魔王想不断折磨他),当他死亡后,会自动重生在那里。但他重生完毕后,魔王刚好会再次离开地牢。经过若干次的尝试(作死),Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢,如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。 "}},{"title":"输入","value":{"format":"PLAIN","content":"每组测试数据的第一行有三个整数n,m,t(2\u0026lt;\u003dn,m\u0026lt;\u003d20,t\u0026gt;0)。接下来的n行m列为地牢的地图,其中包括: “.” 代表路, “* ”代表墙 ,“@” 代表Ignatius的重生点 ,“^” 代表地牢的出口 ,A-J 代表带锁的门,对应的钥匙分别为a-j ;a-j 代表钥匙,对应的门分别为A-J ;每组测试数据之间有一个空行。 "}},{"title":"输出","value":{"format":"PLAIN","content":"针对每组测试数据,如果可以成功逃亡,请输出需要多少分钟才能离开,如果不能则输出-1。 "}},{"title":"样例输入","value":{"format":"PLAIN","content":"4 5 17\n@A.B.\na*.*.\n*..*^\nc..b*\n\n4 5 16\n@A.B.\na*.*.\n*..*^\nc..b*"}},{"title":"样例输出","value":{"format":"PLAIN","content":"16\n-1"}}]}