A4407 | $【算法】Gold King勇闯八卦图2$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

青青草原上的神奇八卦图，每隔几个月，就会发生变化，内部暗格会移动。 Gold King对这个神秘的八卦图好奇更胜，觉得凭借自己的聪敏才智，不可能进去出不来，上次只花几步就能走出来，这次想知道最少需要多少步。于是Gold King来到了八卦图入口，得知八卦图的规模n行m列，由'.'构成的可以走的路，由'X'构成的墙壁，可以沿上下左右四个方向移动。试着根据给定的入口和出口，计算一下Gold King走出八卦图的最少步数。

输入格式

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

输出格式

对于每组测试数据输出一行最少步数。

输入输出样例

输入 #1

2
10 10
XSXXXXXX.X
......X..X
.X.XX.XX.X
.X........
XX.XX.XXXX
....X....X
.XXXXXXX.X
....X.....
.XXXX.XXX.
....X...TX
10 10
XSXXXXXX.X
X........X
XXXXXXXX.X
X........X
X.XXXXXXXX
X........X
XXXXXXXX.X
X........X
X.XXXXXXXX
X.......TX

输出 #1

23
45

C++ 编辑器

输入

输出

A4407 | 【算法】Gold King勇闯八卦图2

题目描述

输入格式

输出格式

输入输出样例

A4407 | $【算法】Gold King勇闯八卦图2$