Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
2.7 kB
2
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, m, x, y, xb, yb, ans;
	static char[][] map;
	static int[][] visit;
	static int[] dxZ = { 1, 2, 1, 2, -2, -1, -2, -1 };
	static int[] dyZ = { 2, 1, -2, -1, -1, -2, 1, 2 };
	static int[] dxA = { 1, -1, 1, -1, 0, 0, 1, -1 };
	static int[] dyA = { 1, -1, -1, 1, 1, -1, 0, 0 };
	static Queue queue = new Queue(200000);

	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("src/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			m = sc.nextInt();
			n = sc.nextInt();
			sc.nextLine();
			map = new char[n][m];
			visit = new int[n][m];
			queue.reset();
			for (int i = 0; i < n; i++) {
				map[i] = sc.next().toCharArray();
				for (int j = 0; j < m; j++) {
					if (map[i][j] == 'A') {
						x = i;
						y = j;
					}
					if (map[i][j] == 'B') {
						xb = i;
						yb = j;
					}
					if (map[i][j] == 'Z') {
						queue.push(i);
						queue.push(j);
					}
				}
			}

			int r, c;
			while (!queue.empty()) {
				r = queue.pop();
				c = queue.pop();
				for (int i = 0; i < 8; i++) {
					int nr = r + dxZ[i];
					int nc = c + dyZ[i];

					if (nr >= 0 && nr < n && nc >= 0 && nc < m && map[nr][nc] == '.') {
						map[nr][nc] = 'X';
					}
				}

			}

			queue.reset();
			queue.push(x);
			queue.push(y);
			visit[x][y] = 1;
			while (!queue.empty()) {
				r = queue.pop();
				c = queue.pop();
				for (int i = 0; i < 8; i++) {
					int nr = r + dxA[i];
					int nc = c + dyA[i];

					if (nr >= 0 && nr < n && nc >= 0 && nc < m&&visit[nr][nc]==0 && map[nr][nc]=='.') {
						visit[nr][nc] = visit[r][c]+1;
						queue.push(nr);
						queue.push(nc);
					}
				}
			}
			int min = 10000;
			for (int i = 0; i < 8; i++) {
				int nr = xb + dxA[i];
				int nc = yb + dyA[i];

				if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
					if(visit[nr][nc]!=0) {
						if(min>visit[nr][nc]) {
							min = visit[nr][nc];
						}
					}

				}
			}
			if(min==10000) {
				ans=-1;
			}else {
				ans=min;
			}
			System.out.println(ans);

		}
		sc.close();
	}

}

class Queue {
	static int r, f;
	static int arr[];

	Queue(int c) {
		arr = new int[c];
		f = r = 0;
	}

	boolean empty() {
		return f == r;
	}

	int pop() {
		int tmp = arr[f];
		f++;
		return tmp;
	}

	void push(int data) {
		arr[r] = data;
		r++;
	}

	void reset() {
		r = f = 0;
	}
}