Untitled

///taiiii
Crazyyy Kinggg

#include <iostream>
using namespace std;

char map[505][505];
int n, m, start, last;
int dx[] = { 1,-1,-2,-2,-1,1,2,2 };
int dy[] = { 2,2,1,-1,-2,-2,-1,1 };
int dxk[] = { -1,0,0,1,-1,1,1,-1 };
int dyk[] = { 0,1,-1,0,1,1,-1,-1 };
int cnt[505][505];
int visited[505][505];
int xStart, yStart, xTarget, yTarget;
int xQueue[2000000];
int yQueue[2000000];


void BFSZ() {
	int xCur, yCur, xNext, yNext;
	while (start != last) {
		xCur = xQueue[start];
		yCur = yQueue[start++];
		visited[xCur][yCur] = 1;
		for (int i = 0; i < 8; i++) {
			xNext = xCur + dx[i];
			yNext = yCur + dy[i];
			if (xNext >= 0 && xNext < n && yNext >= 0 && yNext < m && visited[xNext][yNext] == 0 && map[xNext][yNext] != 'A' && map[xNext][yNext] != 'B') {
				visited[xNext][yNext] = 1;
				cnt[xNext][yNext] = -1;
				/*xQueue[last] = xNext;
				yQueue[last++] = yNext;*/
			}
			
		}
	}
}

void BFSA() {
	start = 0; last = 0;
	xQueue[last] = xStart;
	yQueue[last++] = yStart;
	visited[xStart][yStart] = 1;
	int xCur, yCur;
	int xNext, yNext;
	while (start != last) {
		xCur = xQueue[start];
		yCur = yQueue[start++];
		for (int i = 0; i < 8; i++) {
			xNext = xCur + dxk[i];
			yNext = yCur + dyk[i];
			if (xNext >= 0 && xNext < n && yNext >= 0 && yNext < m && map[xNext][yNext] != 'Z') {
				if (visited[xNext][yNext] == 0 || cnt[xNext][yNext] > cnt[xCur][yCur] + 1) {
					cnt[xNext][yNext] = cnt[xCur][yCur] + 1;
					xQueue[last] = xNext;
					yQueue[last++] = yNext;
					visited[xNext][yNext] = 1;
				}
				if (map[xNext][yNext] == 'B') {
					return;
				}
			}
		}
	}
}

int main()
{
	FILE* stream;
	freopen_s(&stream, "Text.txt", "r", stdin);
	int T;
	cin >> T;
	start = 0;
	last = 0;
	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++) {
				visited[i][j] = 0;
				cnt[i][j] = 0;
				if (map[i][j] == 'A') {
					xStart = i;
					yStart = j;
				}
				if (map[i][j] == 'B') {
					xTarget = i;
					yTarget = j;
				}
				if (map[i][j] == 'Z') {
					visited[i][j] = 1;
					cnt[i][j] = -1;
					xQueue[last] = i;
					yQueue[last++] = j;
				}
			}
		}
		BFSZ();
		BFSA();
		if (cnt[xTarget][yTarget] == 0) {
			cnt[xTarget][yTarget] = -1;
		}
		cout << cnt[xTarget][yTarget] << endl;
	}
	return 0;
}