# Untitled

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;
}
}```