#include<algorithm>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
char c;
int sgn;
if(c=getchar(),c==EOF) return 0; //EOF
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
inline void outt(ll x) {
if(x>9) outt(x/10);
putchar(x%10+'0');
}
const int maxn = 10005;
char g[maxn][maxn];
int vis[maxn][maxn];
struct ss{
int x,y,step;
ss(int _x=0,int _y=0,int _step=0):x(_x),y(_y),step(_step){
}
};
int dir[6][2] = {1,3,1,-3,-1,3,-1,-3,2,0,-2,0};
int stx,sty;
int edx,edy;
int n,m;
bool ok(int x,int y){
if(x>0&&x<=n&&y>0&&y<=m&&vis[x][y]==0&&(g[x][y]==' '||g[x][y]=='T'))return true;
return false;
}
int bfs(){
queue<ss>q;
while(!q.empty()) q.pop();
q.push(ss{stx,sty,1});
vis[stx][sty] = 1;
while(!q.empty()){
int x=q.front().x, y=q.front().y, step=q.front().step;
if(x==edx&&y==edy) return step;
q.pop();
rep(i,0,5){
int xx = x+dir[i][0], yy = y+dir[i][1];
if(ok(xx,yy)){
vis[xx][yy]=1;
int xxx=xx+dir[i][0], yyy = yy+dir[i][1];
if(ok(xxx,yyy)){
vis[xxx][yyy]=1;
q.push(ss{xxx,yyy,step+1});
}
}
}
}
return -1;
}
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%d%d", &n,&m);
getchar();
n = n*4+3, m = m*6+3;
rep(i,1,n){
gets(g[i]);
rep(j,1,m){
if(g[i][j]=='\0'){
break;
}
vis[i][j]=0;
if(g[i][j] == 'S')
stx = i, sty = j;
if(g[i][j] == 'T')
edx = i, edy = j;
}
}
int ans = bfs();
printf("%d\n", ans);
}
return 0;
}
撰写