DFS or BFS?

题目描述

说好了，题目不黑人。

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

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

输入说明

T->测试数据组数(T)。

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

输出说明

对于第i组数据，请输出

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

样例

输入

2
.......A
........
........
........
........
........
........
U.......

.......A
........
........
........
........
.S......
S.......
US......

输出

Case #1: Yes
Case #2: No