Untitled

#include <iostream>
using namespace std;

int n, m;
char arr[101][101];
int dRM[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dCM[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int visited[101][101];
int dRV[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dCV[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int len[101][101];

typedef struct Point{
	int x, y;
};

typedef struct Queue{
	int front, rear;
	Point data[10001];
};

void init(Queue &Q){
	Q.front = Q.rear = -1;
}

void push(Queue &Q, Point value){
	Q.rear++;
	Q.data[Q.rear] = value;
}

Point top(Queue &Q){
	Point temp;
	Q.front++;
	temp = Q.data[Q.front];
	Q.front--;
	return temp;
}

void pop(Queue &Q){
	Q.front++;
}

bool empty(Queue &Q){
	if(Q.front == Q.rear)
		return true;
	return false;
}

Queue Q2;

void BFS(Point P){
	init(Q2);
	push(Q2, P);
	visited[P.x][P.y] = 1;
	len[P.x][P.y] = 0;
	while(!empty(Q2)){
		Point P1;
		P1 = top(Q2);
		pop(Q2);

		for(int k=0; k<8; k++){
			int x = P1.x + dRV[k];
			int y = P1.y + dCV[k];

			if(x>=1 && x<=n && y>=1 && y<=m && visited[x][y] == 0 && arr[x][y] != 'Z'){
				visited[x][y] = 1;
				len[x][y] = len[P1.x][P1.y] + 1;

				if(arr[x][y] == 'B')
					return;

				Point P2;
				P2.x = x;
				P2.y = y;
				push(Q2, P2);
			}

		}
	}
}

Queue Q1;

void sub(){
	
	while(!empty(Q1)){
		Point P;
		P = top(Q1);
		pop(Q1);

		for(int k=0; k<8; k++){
			int x = P.x + dRM[k];
			int y = P.y + dCM[k];

			if(x>=1 && x<=n && y>=1 && y<=m && arr[x][y] == '.'){
				arr[x][y] = 'Z';
			}
		}

	}

}

void reset(){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			visited[i][j] = 0;
			len[i][j] = 0;
		}
	}
}

int main(){
	//freopen("vao.txt", "r", stdin);
	int t;
	cin >> t;
	for(int tc=1; tc<=t; tc++){
		cin >> m >> n;
		int xs = -1, ys = -1;
		int xe = -1, ye = -1;
		init(Q1);

		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				cin >> arr[i][j];

				if(arr[i][j] == 'A' && xs == -1){
					xs = i;
					ys = j;
				}

				if(arr[i][j] == 'B' && xe == -1){
					xe = i;
					ye = j;
				}

				if(arr[i][j] == 'Z'){
					Point P;
					P.x = i;
					P.y = j;
					push(Q1, P);
				}
			}
		}

		reset();

		sub();

		Point P;
		P.x = xs;
		P.y = ys;

		BFS(P);

		if(visited[xe][ye] == 1){
			cout << len[xe][ye] << endl;
		}else{
			cout << "-1" << endl;
		}

		/*for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				cout << arr[i][j] << " ";
			}
			cout << endl;
		}*/
	}
	return 0;
}