|
||||||||||
小明系列故事——捉迷藏Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 3285 Accepted Submission(s): 992 Problem Description 小明的妈妈生了三个孩子,老大叫大明, 老二叫二明, 老三..., 老三自然就叫小明了。 一天,小明的妈妈带小明兄弟三人去公园玩耍,公园里面树木很多,有很多地方可以藏身, 于是他们决定玩捉迷藏。经过几轮的猜拳后,第一轮是小明来找其他两个人,游戏规则很简单: 只要小明可以在规定的时间内找到他们就算小明获胜,并且被发现的两个人猜拳决定谁在下一轮负责找人;如果在规定的时间内只找到一个人,那么没有被发现的人获胜,被找到的人下一轮负责找人;如果在规定的时间内一个人都没有找到,则小明失败了,下一轮还是他来找人。现在小明想知道,在规定时间内,自己是否可以找到所有的人,现在他想请你来帮忙计算一下。 为了简单起见,把公园看成是n行m列的矩阵,其中’S’表示小明,’D’表示大名,’E’表示二明,’X’表示障碍物,’.’表示通路。这里,我们把发现定义为,可以直接看到对方, 也就是说两个人在同一行或者同一列,并且中间没有障碍物或者没有其他人就可以看到对方。并且假设,大明,二明藏好以后就不会再改变位置,小明每个单位时间可以从当前的位置走到相邻的四个位置之一,并且不会走出公园。 Input 测试数据第一行是一个正整数T,表示有T组测试数据。 每一组测试数据首先是三个正整数n,m,t,分别表示行数、列数和规定的时间,接下来n行,每行m个上述的字符,并且保证有且只有一个’S’,一个’E’,一个’D’。 [Technical Specification] T < 200 3 <= n, m <= 100 0 <= t <= 100 Output 每组先输出一行Case c:(c表示当前的组数,从1开始计数); 接下来一行,如果小明可以在规定时间内找到所有的人,则输出最少需要的时间,否则输出-1。 Sample Input
Sample Output
Source | ||||||||||
|