{"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":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n 小明的妈妈生了三个孩子,老大叫大明, 老二叫二明, 老三..., 老三自然就叫小明了。 \n \u003cbr\u003e 一天,小明的妈妈带小明兄弟三人去公园玩耍,公园里面树木很多,有很多地方可以藏身, 于是他们决定玩捉迷藏。经过几轮的猜拳后,第一轮是小明来找其他两个人,游戏规则很简单: \n \u003cbr\u003e 只要小明可以在规定的时间内找到他们就算小明获胜,并且被发现的两个人猜拳决定谁在下一轮负责找人;如果在规定的时间内只找到一个人,那么没有被发现的人获胜,被找到的人下一轮负责找人;如果在规定的时间内一个人都没有找到,则小明失败了,下一轮还是他来找人。现在小明想知道,在规定时间内,自己是否可以找到所有的人,现在他想请你来帮忙计算一下。 \n \u003cbr\u003e 为了简单起见,把公园看成是n行m列的矩阵,其中’S’表示小明,’D’表示大名,’E’表示二明,’X’表示障碍物,’.’表示通路。这里,我们把发现定义为,可以直接看到对方, 也就是说两个人在同一行或者同一列,并且中间没有障碍物或者没有其他人就可以看到对方。并且假设,大明,二明藏好以后就不会再改变位置,小明每个单位时间可以从当前的位置走到相邻的四个位置之一,并且不会走出公园。 E和D也不能走。\n \u003cbr\u003e \n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"测试数据第一行是一个正整数T,表示有T组测试数据。 \n\u003cbr\u003e每一组测试数据首先是三个正整数n,m,t,分别表示行数、列数和规定的时间,接下来n行,每行m个上述的字符,并且保证有且只有一个’S’,一个’E’,一个’D’。 \n\u003cbr\u003e \n\u003cbr\u003e \n\u003cb\u003e[Technical Specification]\u003c/b\u003e \n\u003cbr\u003eT \u0026lt; 200 \n\u003cbr\u003e3 \u0026lt;\u003d n, m \u0026lt;\u003d 100 \n\u003cbr\u003e0 \u0026lt;\u003d t \u0026lt;\u003d 100 \n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"每组先输出一行Case c:(c表示当前的组数,从1开始计数); \n\u003cbr\u003e接下来一行,如果小明可以在规定时间内找到所有的人,则输出最少需要的时间,否则输出-1。 \n\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e3\n5 6 3\nXXD...\n....E.\n....X.\n....S.\n......\n5 6 3\nXDX...\n....E.\n......\n....S.\n......\n5 6 8\nXXDX..\n.XEX..\n......\n....S.\n......\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003eCase 1:\n-1\nCase 2:\n3\nCase 3:\n-1\u003c/pre\u003e"}}]}