问题 4054 --DFS or BFS?

4054: DFS or BFS?

时间限制: 1 Sec  内存限制: 128 MB
提交: 7  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][24kb]

题目描述

说好了,题目不黑人。

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

提示

来源

[提交][状态]