Untitled

package Battle_City;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, m, xstart, ystart, xend, yend, res;
	static int[][] visit, lan;
	static char[][] a;
	static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 },
			queueX = new int[9000005], queueY = new int[9000005];

	public static void BFS() {
		int front = 0, rear = 0;
		queueX[front] = xstart;
		queueY[front] = ystart;
		lan[xstart][ystart] = 0;
		visit[xstart][ystart] = 1;
		while (front <= rear) {
			int x = queueX[front], y = queueY[front];
			int c = lan[x][y];
			visit[x][y] = 2;
			for (int i = 0; i < 4; i++) {
				int newx = x + dx[i], newy = y + dy[i];
				if (newx >= 0 && newy >= 0 && newx < n && newy < m
						&& a[newx][newy] != 'R' && a[newx][newy] != 'S') {
					if (a[newx][newy] == 'B') {
						if (visit[newx][newy] == 0) {
							rear++;
							queueX[rear] = newx;
							queueY[rear] = newy;
							visit[newx][newy] = 1;
							lan[newx][newy] = c + 2;
						}else if (visit[newx][newy] == 2 && c+2 <lan[newx][newy]) {
							rear++;
							queueX[rear] = newx;
							queueY[rear] = newy;
							visit[newx][newy] = 1;
							lan[newx][newy] = Math.min(c + 2, lan[newx][newy]);
						}else{
							lan[newx][newy] = Math.min(c + 2, lan[newx][newy]);
						}
					}
					if (a[newx][newy] == 'E') {
						if (visit[newx][newy] == 0) {
							rear++;
							queueX[rear] = newx;
							queueY[rear] = newy;
							visit[newx][newy] = 1;
							lan[newx][newy] = c + 1;
						}else if (visit[newx][newy] == 2 && c+1 <lan[newx][newy]) {
							rear++;
							queueX[rear] = newx;
							queueY[rear] = newy;
							visit[newx][newy] = 1;
							lan[newx][newy] = Math.min(c + 1, lan[newx][newy]);
						} else {
							lan[newx][newy] = Math.min(c + 1, lan[newx][newy]);
						}
					}
					if (a[newx][newy] == 'T') {
						if (visit[newx][newy] == 0) {
							rear++;
							queueX[rear] = newx;
							queueY[rear] = newy;
							visit[newx][newy] = 1;
							lan[newx][newy] = c + 1;
						} else {
							lan[newx][newy] = Math.min(c + 1, lan[newx][newy]);
						}
					}
				}

			}
			front++;
		}

	}

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			n = scanner.nextInt();
			m = scanner.nextInt();
			a = new char[n][m];
			visit = new int[n][m];
			lan = new int[n][m];
			for (int i = 0; i < n; i++) {
				String s = scanner.next();
				for (int j = 0; j < m; j++) {
					a[i][j] = s.charAt(j);
					if (a[i][j] == 'Y') {
						xstart = i;
						ystart = j;
					}
					if (a[i][j] == 'T') {
						xend = i;
						yend = j;
					}
				}
			}
			res = 0;

			BFS();

			// for (int i = 0; i < n; i++) {
			// for (int j = 0; j < m; j++) {
			// System.out.print(lan[i][j] + " ");
			// }
			// System.out.println();
			// }

			if (visit[xend][yend] == 0) {
				res = -1;
			} else {
				res = lan[xend][yend];
			}

			System.out.println("Case #" + t + "\n" + res);
		}
		scanner.close();
	}
}