Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.1 kB
1
Indexable
Never
#include <iostream>

using namespace std;

int M,N;
char A[105][105];
int danger[105][105];

int sr,sc,er,ec;

int Qx[11000] = {0};
int Qy[11000] = {0};

int r = -1;
int f = -1;

int vis[105][105] = {0};

int dxma[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dyma[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

int dxvua[8] = {-1,-1,0,1,1,1,0,-1};
int dyvua[8] = {0,1,1,1,0,-1,-1,-1};

int ans= 100000;

void Push(int x, int y){
	r++;
	Qx[r] = x;
	Qy[r] = y;
}

void Pop(int &x, int &y){
	f++;
	x = Qx[f];
	y = Qy[f];
}

void BFS(int sR, int sC){
	Push(sR,sC);
	vis[sR][sC] = 1;
	while(r!=f){
		Pop(sR,sC);
		int nR,nC;
		for (int i = 0; i < 8; i++){
			nR = sR + dxvua[i];
			nC = sC + dyvua[i];
			if ( nR >= 0 && nR <= M-1 && nC >=0 && nC <= N-1){
				if (danger[nR][nC] == 0 && vis[nR][nC] == 0){
					Push(nR,nC);
					vis[nR][nC] = vis[sR][sC] + 1;
					if (nR == er && nC == ec){
						ans = vis[sR][sC] + 1;
					}
				}
			}
		}
	}
}

int main(){
	//freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++){
		cin >> N >> M;
		// reset
		ans = 100000;
		r=f=-1;
		for (int i = 0; i < M; i++){
			for ( int j = 0; j < N; j++){
				vis[i][j] = 0;
				danger[i][j] = 0;
			}
		}
		for (int i = 0; i < M; i++){
				cin >> A[i];
		}
		for (int i = 0; i < M; i++){
			for ( int j = 0; j < N; j++){
				if (A[i][j] == 'A'){
					sr = i;
					sc = j;
				}
				if (A[i][j] == 'B'){
					er = i;
					ec = j;
				}
			}
		}
		// add danger
		for (int i = 0; i < M; i++){
			for ( int j = 0; j < N; j++){
				if (A[i][j] == 'Z'){
					danger[i][j] = 1;
					int xtmp,ytmp;
					for ( int k = 0; k < 8; k++){
						xtmp = i + dxma[k];
						ytmp = j + dyma[k];
						if (xtmp >= 0 && xtmp <= M-1 && ytmp >= 0 && ytmp <= N-1){
							danger[xtmp][ytmp] = 1;
						}
					}
				}
			}
		}
		danger[sr][sc] = danger[er][ec] = 0;
		BFS(sr,sc);
		if (ans != 100000){
			cout << ans-1 << endl;
		}
		else cout << -1 << endl;
	}


	return 0;
}