battle city

#include <iostream>
#define MAX_Q 80000
using namespace std;
char map[1005][1005];
int visited[1005][1005];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

int m, n;

#define QUEUE_SIZE 1000000

struct Node {
    int x, y;
    int step; // Add a priority attribute
};

Node q[QUEUE_SIZE];
int front = 0, rear = 0;

void insertSorted(Node p) {
    int i;
    for (i = rear - 1; (i >= front) && (q[i].step > p.step); i--) {
        q[i + 1] = q[i]; // Moving each element one position ahead to make space for the new element
    }
    q[i + 1] = p; // Insert the new element at the correct position
    rear++;
}

void push(Node p) {
    if (rear == QUEUE_SIZE) {
        throw std::runtime_error("Queue is full");
    }
    insertSorted(p); // Insert the element in the sorted order
}

bool isEmpty() {
    return front == rear;
}

Node pop() {
    if (isEmpty()) {
        throw std::runtime_error("Queue is empty");
    }
    return q[front++]; // Remove the element from the front
}


bool check(int x, int y) {
	if (x < 0 || x >= m || y < 0 || y >= n)
	{
		return true;
	}
	if (map[x][y] == 'S' || map[x][y] == 'R')
	{
		return true;
	}
	if (visited[x][y])
	{
		return true;
	}
	return false;
}

int bfs(int x, int y ) {
    front = rear = 0;
    Node p,temp;
    p.x = x;
    p.y = y;
    p.step = 0;

    
    visited[x][y] = 1;

    push(p);

    while (!isEmpty()) {
        p = pop();

        for (int i = 0; i < 4; i++) {
            temp.x = p.x + dx[i];
            temp.y = p.y + dy[i];

            if (check(temp.x,temp.y))
                continue;

            if (map[temp.x][temp.y] == 'B')
                temp.step = p.step + 2;
            else
                temp.step = p.step + 1;

            if (map[temp.x][temp.y] == 'T')
                return temp.step;

            visited[temp.x][temp.y] = 1;
            push(temp);
        }
    }
    return -1;
}




int main() {
	int T;
	int sx{}, sy{};
	//FILE* inputFile = freopen("input.txt","r",stdin);
	cin >> T;
	for (int tc = 0; tc < T; tc++)
	{
		cin >> m >> n;
        if (m == 0 || n == 0)
        {
            break;
        }
		memset(map,' ',sizeof(map));
		memset(visited, 0, sizeof(visited));
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				cin >> map[i][j];
				if (map[i][j] == 'Y')
				{
					sx = i;
					sy = j;
				}
			}
		}
		cout <<"#"<<tc+1<<" "<< bfs(sx, sy) << endl;
	}
	return 0;
}