battlesol

#include <iostream>

using namespace std;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

char a[400][400];
int dist[400][400];

int n, m;

int queueX[1000005], queueY[1000005];
int x_start, y_start, x_end, y_end;
int start, last;
int check = 0;

void reset() {
	
	for (int i = 0; i < 400; i++) {
		for (int j = 0; j < 400; j++) {
			dist[i][j] = 0;
		}
	}
}

void bfs() {
	reset();
	start = 0;
	last = 0;
	
	int x_cur, y_cur, x_next, y_next;
	queueX[last] = x_start;
	queueY[last++] = y_start;
	dist[x_start][y_start] = 1;
	
	while (start != last) {
		x_cur = queueX[start];
		y_cur = queueY[start++];
		
		for (int i = 0; i < 4; i++) {
			x_next = x_cur + dx[i];
			y_next = y_cur + dy[i];
			if (x_next >= 1 && x_next <= n && y_next >= 1 && y_next <= m) {
				if (a[x_next][y_next] == 'E') {
					if (dist[x_next][y_next] == 0 || dist[x_next][y_next] > dist[x_cur][y_cur] + 1) {
						dist[x_next][y_next] = dist[x_cur][y_cur] + 1;
						queueX[last] = x_next;
						queueY[last++] = y_next;
					}
				}
				if (a[x_next][y_next] == 'B') {
					if (dist[x_next][y_next] == 0 || dist[x_next][y_next] > dist[x_cur][y_cur] + 2) {
						dist[x_next][y_next] = dist[x_cur][y_cur] + 2;
						queueX[last] = x_next;
						queueY[last++] = y_next;
					}
				}
				if (a[x_next][y_next] == 'T') {
					if (dist[x_next][y_next] == 0 || dist[x_next][y_next] > dist[x_cur][y_cur] + 1) {
						dist[x_next][y_next] = dist[x_cur][y_cur] + 1;
					}
				}
			}
		}
	}
	
	
	
	
	
}

void solve(int testcase) {
	cin >> n >> m;
	
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if (a[i][j] == 'Y') {
				x_start = i;
				y_start = j;
			}
			if (a[i][j] == 'T') {
				
				x_end = i;
				y_end  = j;
			}
		}
		
	}
	bfs();
	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << dist[i][j] << " ";
		}
		cout << endl;
	}
	*/
	// de mang dist la 0 neu ko di duoc - ans di 1 la xong
	int ans = dist[x_end][y_end];
	cout << "Case #" << testcase << endl;
	cout << ans  - 1<< endl;
	
}

int main() {
	freopen("Text.txt", "r", stdin);
	int t; cin >> t;
	
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
	
	
}