import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner;
public class RobotMaze {
static int[][] maze; static int[][] queue; static boolean[][][] isD; static int[][] dir = new int[][] { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; static int head; static int tail; static int minstep; public static void main(String[] args) throws FileNotFoundException { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); sc = new Scanner(new File("files/robotmaze")); int T = sc.nextInt(); for (int t = 0; t < T; t++) { int M = sc.nextInt(); int N = sc.nextInt(); minstep = M * N * 3; isD = new boolean[M + 1][N + 1][4]; maze = new int[M + 2][N + 2]; queue = new int[M * N * 10][4]; for (int i = 0; i < M + 2; i++) { maze[i][0] = 0; maze[i][N + 1] = 0; } for (int i = 0; i < N + 2; i++) { maze[0][i] = 0; maze[M + 1][i] = 0; } char[] tmpr; int sx = 0, sy = 0; for (int i = 1; i < M + 1; i++) { tmpr = sc.next().toCharArray(); for (int j = 1; j < N + 1; j++) { if (tmpr[j - 1] == '#') maze[i][j] = 0; else if (tmpr[j - 1] == '.') maze[i][j] = 1; else if (tmpr[j - 1] == 'S') { sx = i; sy = j; maze[i][j] = 2; } else { maze[i][j] = -1; } } } head = 0; tail = 0; queue[tail++] = new int[] { sx, sy, 0, 0 }; BFS2(); if (minstep == M * N * 3) System.out.println(-1); else System.out.println(minstep); } } private static void BFS2() { // TODO Auto-generated method stub while (true) { if (head == tail) return; int x = queue[head][0]; int y = queue[head][1]; int step = queue[head][2]; int pdir = queue[head][3]; int nx, ny, ndir; for (int i = 1; i < 4; i++) { ndir = (pdir + i + 2) % 4; if (ndir == pdir) { isD[x][y][ndir] = true; nx = x + dir[ndir][0]; ny = y + dir[ndir][1]; if (maze[nx][ny] == 1) { maze[nx][ny] = 2; queue[tail++] = new int[] { nx, ny, step + 1, ndir }; } else if (maze[nx][ny] == -1) { minstep = step + 1; return; } } else if (!isD[x][y][ndir]) { queue[tail++] = new int[] { x, y, step + 1, ndir }; } } head++; } }}
sample input: 3 5 5 ##### #…# #.#.# #S#T# ##### 4 5 #.#.# #.#.# #S#T# ##### 100 100 S……………………………………………………………………………………… ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………. ………………………………………………………………………………………T
sample output: 8 -1 200
