Untitled

import java.util.Scanner;

public class Solution {

	static Scanner scanner=new Scanner(System.in);
	
	static class Node{
		int x,y,cost;
		Node link;
		Node(int x,int y,int cost){
			this.x=x;
			this.y=y;
			this.cost=cost;
		}
	}
	
	static class Queue{
		Node front;
		int n;
		void push(Node node){
			Node tmp=front;
			++n;
			
			if(front==null)
				front=node;
			else if(node.cost<front.cost){
				node.link=front;
				front=node;
			}
			else{
				while(tmp.link!=null && node.cost>tmp.link.cost)
					tmp=tmp.link;
				node.link=tmp.link;
				tmp.link=node;
			}
		}
		void pop(){
			if(front==null)
				return;
			--n;
			front=front.link;
		}
	}
	
	static void exec(int test){
		int n=Integer.parseInt(scanner.next()),m=Integer.parseInt(scanner.next());
		/*m,n: me cung m hang, n cot
		 * ko the di qua cac con song hay tuong, nhung co the pha huy tuong gach
		 * bang cach ban no
		 * buc tuong gach tro thanh rong neu ban gap no
		 * tuong thep thi ko the hit
		 * moi lan chi dc di chuyen 4 huong
		 * hoac ban vao 1 trong 4 huong
		 * ma ko di chuyen
		 * viec ban se di thang
		 * can it nhat bao nhieu luot de den dc target
		 * o moi vi tri thi dc di chuyen hoac ban vao 1 trong 4 cai ma ko di chuyeb 
		 * */
		char[][] a=new char[n][m];
		int[][] cost=new int[n][m];
		int sx=-1,sy=-1,ex=-1,ey=-1;
		
		for(int i=0;i<n;++i){
			char[] tmp=scanner.next().toCharArray();
			for(int j=0;j<m;++j){
				a[i][j]=tmp[j];
				if(tmp[j]=='Y'){
					sx=i;sy=j;
				}else if(tmp[j]=='T'){
					ex=i;ey=j;
				}
			}
		}
		
		for(int i=0;i<n;++i) for(int j=0;j<m;++j)
			cost[i][j]=Integer.MAX_VALUE;
		cost[sx][sy]=0;
		
		int[][] dir={{0,-1},{0,1},{-1,0},{1,0}};
		Queue queue=new Queue();
		queue.push(new Node(sx,sy,0));
		while(queue.n>0){
			int x=queue.front.x,y=queue.front.y,cost1=queue.front.cost;
			queue.pop();
			
			if(cost1>cost[x][y]) continue;
			
			for(int i=0;i<4;++i){
				int nx=x+dir[i][0],ny=y+dir[i][1];
				if(nx>=0 && nx<n && ny>=0 && ny<m && a[nx][ny]!='S' && a[nx][ny]!='R'){
					if(a[nx][ny]=='B' && cost[nx][ny]>cost[x][y]+2){
						cost[nx][ny]=cost[x][y]+2;
						queue.push(new Node(nx,ny,cost[nx][ny]));
					}
					else if((a[nx][ny]=='E' || a[nx][ny]=='T') && cost[nx][ny]>cost[x][y]+1){
						cost[nx][ny]=cost[x][y]+1;
						queue.push(new Node(nx,ny,cost[nx][ny]));
					}
				}
			}
		}
		
		System.out.printf("Case #%d\n%d\n",test,cost[ex][ey]==Integer.MAX_VALUE?-1:cost[ex][ey]);
	}
	
	public static void main(String[] args) {
		
		int t=Integer.parseInt(scanner.next());
		
		for(int test=1;test<=t;++test)
			exec(test);
		
		scanner.close();
	}
}