Untitled

Battle City

//tgt
//test
//doan code chua dung lam

#include<iostream>
using namespace std;
char map[500][500];
int check[500][500];
int visited[500][500];
int x, y, t, z;
int n, m;
int start, last;
int xCur, yCur, xNext, yNext;
int xQueue[500];
int yQueue[500];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

void BFS(int x, int y) {
	start = 0;
	last = 0;
	visited[x][y] = 1;
	check[x][y] = 0;
	xQueue[last] = x;
	yQueue[last++] = y;
	
	while (start != last) {
		xCur = xQueue[start];
		yCur = yQueue[start++];
		visited[xCur][yCur] = 1;
		for (int i = 0; i < 4; i++) {
			xNext = xCur + dx[i];
			yNext = yCur + dy[i];
			if (visited[xNext][yNext] == 0 && xNext >= 0 && xNext < n && yNext >= 0 && yNext < m && map[xNext][yNext] != 'S' && map[xNext][yNext] != 'R') {
				
				xQueue[last] = xNext;
				yQueue[last++] = yNext;
				if (map[xNext][yNext] == 'E' && (check[xNext][yNext] > check[xCur][yCur] + 1 || check[xNext][yNext] == 0)) {
					check[xNext][yNext] = check[xCur][yCur] + 1;
				}
				if (map[xNext][yNext] == 'B' && (check[xNext][yNext] > check[xCur][yCur] + 2 || check[xNext][yNext] == 0)) {
					check[xNext][yNext] = check[xCur][yCur] + 2;
				}
				if (map[xNext][yNext] == 'T' && (check[xNext][yNext] > check[xCur][yCur] + 1 || check[xNext][yNext] == 0)) {
					check[xNext][yNext] = check[xCur][yCur] + 1;
				}
			}
		}
	}
}

int main() {
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
	
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			cin >> map[i];
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 'Y') {
					x = i;
					y = j;
				}
				if (map[i][j] == 'T') {
					t = i;
					z = j;
				}
				visited[i][j] = 0;
				check[i][j] = 0;
			}
		}
		BFS(x, y);
		cout << "Case #" << tc << " " << check[t][z] << endl;
	}
	return 0;
}