Problem1553--动态路径规划

1553: 动态路径规划

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

给你一个8*8的矩阵,你的初始位置是左下角方格(用'U’表示),你的目标位置是右上角的方格('A'表示),其余的62个方格,如果是'.',表示这个方格为空,如果是'S',表示这个方格有一块大石头。好了现在你开始从左下角出发,每次可以往上,下,左,右,左上,右上,左下,右下移动一个方格,或者你可以原地不动,一共九个动作方式,在你做完一个动作后,所有的大石头会往下掉一个方格(如果一个大石头的位置是(xy,那下一秒是(x+1y,不过如果它已经在最下面的一排了,那它就会掉出矩阵,不再出现),请注意,任一时刻,你不能和某一个大石头处在同一个方格,否则石头会把你XX掉。

现在的问题就是:你能从左下角安全抵达右上角么? 如果能,输出“Yes”,反之,“No”。

Input

整数T,代表测试数据组数(T)

对于每组数据,输入一个8*8的矩阵,其后有一空行。描述如上。

Output

对于第i组数据,请输出

Case #i: s(s是一个字符串,如果可以到达,则s为“Yes”,反之“No)

Sample Input Copy

1
.......A
........
........
........
........
........
........
U.......


Sample Output Copy

Case #1: Yes

Source/Category