A30928.【算法】Gold King勇闯八卦图

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

青青草原地广人稀,出现一些奇特的事情,总会让人联想到神秘的力量。在草原的西北方向有一处八卦图,相传是伏羲当年经过外星人的提示,而试验捣鼓出来的,会让进去的人出不来。
Gold King对这个神秘的八卦图很好奇,觉得凭借自己的聪敏才智,不可能进去出不来,而且只需要花c步就能走出来(不会为了凑步数,走重复的位置,Gold King就是这么自信)。于是Gold King来到了八卦图入口,得知八卦图的规模n行m列,由'.'构成的可以走的路,由'X'构成的墙壁,可以沿上下左右四个方向移动。试着根据给定的入口和出口

输入格式

第一行输入整数T表示有T组测试数据。
第二行输入三个整数n,m和c,表示规模n行m列,和c步走出八卦图。
接下来输入八卦图信息。'.'表示路,'X'表示墙壁,'S'表示入口,'T'表示出口。

输出格式

对于每组测试数据输出一行“YES”表示能够走出,“NO”表示走不出。

输入输出样例

  • 输入#1

    3
    9 10 13
    S..XXXX...
    X...XX...X
    X..XXXX..X
    X..X..X..X
    X..X..X..X
    X..X..X..X
    X..XXXX..X
    X...XX...X
    ...TXXX...
    4 4 5
    S.X.
    ..X.
    ..XT
    ....
    3 4 5
    S.X.
    ..X.
    ...T
    

    输出#1

    YES
    NO
    YES
    

说明/提示

2 <=n <=10
2 <=m <=10
1 <=c <=100
Gold King的c步不是最短的步数。是刚好c步走出八卦图,且起点出发位置步数为0。

首页