#D. 迷宫搜索

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

我们用一个二维的字符数组来表示前面画出的迷宫：

S**.
....
***T

其中字符S表示起点，字符T表示终点，字符*表示墙壁，字符.表示平地。你需要从S出发走到T，每次只能向上下左右相邻的位置移动，不能走出地图，也不能穿过墙壁，每个点只能通过一次。你需要编程来求解出一种从起点到终点的走法。

第一行输入两个整数 $n (1 \le x \le 100), m(1\le m \le 100)$ 代表迷宫行数和列数。

接下来是一个n×m的矩阵，矩阵中的元素为.、*、S或者T

如果能从起点到达终点输出Yes，否则输出No。

3 4
S**.
....
.**T

Yes

5 6
**S**.
*.....
..*... 
.*****
.....T

Yes

5 6
***.*S
*.....
..*..* 
.**.*.
...*.T

No